A region has N towns numbered 1 to N, and M roads numbered 1 to M.
The i-th road connects town Ai and town Bi bidirectionally with length Ci .
Find the maximum possible total length of the roads you traverse when starting from a town of your choice and getting to another town without passing through the same town more than once.
有一个 N 个点 M 条边的无向图。
第 i 条边的长度为 C_i。
求出图中最长的简单路径的长度。
The input is given from Standard Input in the following format:
N M
A1 B1 C1
A2 B2 C2
...
AM BM CM
Print the answer.
4 4 1 2 1 2 3 10 1 3 100 1 4 1000
1110
10 1 5 9 1
1
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
20
- 2\ \leq\ N\ \leq\ 10
- 1\ \leq\ M\ \leq\ \frac{N(N-1)}{2}
- 1\leq\ A_i\ <\ B_i\ \leq\ N
- 1\leq\ C_i\ \leq\ 10^8
| Time Limit | 1 second |
| Memory Limit | 128 MB |