题目描述

一张无向图有 $N$ 个点（编号为 $1 \sim N$ ）， $M$ 条边，且保证任意两个点之间最多只有一条边。

请编程求解出，该图中从任意点出发，可以走出的最长路的长度是多少？

请注意：在图的遍历过程中，不会重复访问同一个点。

输入

第 $1$ 行有 $2$ 个整数 $N$ 和 $M$ ；

接下来 $M$ 行，每行有 $3$ 个整数 $X,Y,L$ ，代表点 $X$ 和点 $Y$ 之间，存在一条长度为 $L$ 的无向边。

输出

输出一个整数，代表图中存在的最长路。

样例

4 6
1 2 10
2 3 20
3 4 30
4 1 40
1 3 50
2 4 60

150

说明

样例 $1$ 解释

从点 $2$ 出发，先去点 $4$ ，再从点 $4$ 去点 $1$ ，再从点 $1$ 去点 $3$ ，路径长度 $=60+40+50=150$ 。

数据范围

$1 \le N \le 1000$ ， $1 \le M \le 250$ ， $1 \le X,Y \le N$ ， $X \neq Y$ ， $1 \le L \le 10^5$ 。

来源

东方博宜OJ