题面翻译

一个有 $M$ 粒子边的 $N$ 粒子。

第 i 个 $M$ 粒子的长度为 $C_i$。

图中最长简单路径的长度。

题目描述。

在一个地区有 $N$ 个城镇，编号从 $1$ 到 $N$；有 $M$ 条道路，编号从 $1$ 到 $M$。

第 i 条道路双向连接城镇 $A_i$ 和城市 $B_i$，长度为 $C_i$。

从你选择的一个城市出发，在不多次经过同一城市的情况下，求经过的道路长度之和的最大值。

输入格式

输入以下列形式从标准输入端输入。

$N$ $M$

$A_1$ $B_1$ $C_1$

$\vdots$

$A_M$ $B_M$ $C_M$

输出格式

输出答案。

样例 #1

样例输入 #1

4 4

1 2 1

2 3 10

1 3 100

1 4 1000

样例输出 #1

1110

示例 #2

样例输入 #2

10 1

5 9 1

样例输出 #2

1

示例 #3

样例输入 #3

10 13

1 2 1

1 10 1

2 3 1

3 4 4

4 7 2

4 8 1

5 8 1

5 9 3

6 8 1

6 9 5

7 8 1

7 9 4

9 10 3

样例输出 #3

20

提示

数据范围

• $2\ \leq\ N\ \leq\ 10$

• $1\ \leq\ M\ \leq\ \frac{N(N-1)}{2}$

• $1\leq\ A_i\ <\ B_i\ \leq\ N$

• $(A_i,B_i)$ 互不相同

• $1\leq\ C_i\ \leq\ 10^8$

• 所有输入都是整数

示例解释 1

如果我们移动 $4\to\ 1\to\ 3\to\ 2$，我们经过的道路的长度总和为 $1110$。

示例说明 2

可能有一些城镇没有道路连接。

示例解释 3

! \ЈFig. 1