题面描述

有一个 $N$ 个点 $M$ 条边的无向图。

第 $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$

Sample Explanation 1

$4\to\ 1\to\ 3\to\ 2$ と移動すると、通る道路の長さの和は $1110$ となります。

Sample Explanation 2

道路と繋がっていない街が存在するかもしれません。

Sample Explanation 3