题目描述

给定一个含 (n) 个点、(m) 条边的带权无向图。定义两点之间的距离为它们之间最短路径的长度。请你求出所有点对最短路径中的最大值，即图的直径。

格式

输入

第一行两个整数 (n, m)（(1 <= n <= 100)）。 接下来 (m) 行，每行三个整数 (u, v, w)，表示点 (u) 与点 (v) 之间有一条权值为 (w) 的无向边（(1 <= w <= 100)）。

注意：

• 图中可能存在重边，按权值较小者等价处理。
• 题目保证图为连通图。

输出

输出一个整数，表示所有点对中最短路径长度的最大值（图的直径）。

样例

3 2
1 2 4
2 3 5

9