Background

本题是 abc317 - C 可以借助此翻译做完后直接进入原网站提交，本题不提供测试数据。

题目描述

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

第 $i$ 条边的长度为 $C_i$。

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

输入格式

第一行输入两个整数 $N,M$

接下来 $M$ 行每行两个数字 $a,b,c$。

输出格式

输出一个答案

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

样例 1 解释

$4\to 1\to3\to2$ 距离最远为 $1110$。

样例 3 图示

数据范围

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