克索尼亚所在的城市由 个交叉路口组成，这些路口之间通过 条双向道路连接。
交叉路口编号为 到 。道路也编号为 到 。第 条道路连接编号为 和 的交叉路口，其长度为 。
已知，通过现有道路可以从任何一个交叉路口到达任何其他交叉路口。任意两个交叉路口之间最多有一条道路。没有连接同一交叉路口的道路。
定义 为交叉路口 和 之间最短路径的长度。
克索尼亚希望找到城市中的两个交叉路口 和 ，使得 在所有可能的 对中是最大的。
第一行包含两个整数 和 (, ) —— 分别表示城市中的交叉路口数量和测试组编号。
接下来的 行，每行包含三个整数 、、 (, )。
保证使用道路可以从任何一个交叉路口到达任何其他交叉路口。
保证没有连接同一交叉路口的道路。
保证任意两个交叉路口之间最多有一条道路。
输出所有交叉路口对 中最大的 值。
4 0 1 2 1 1 3 2 2 3 3 2 4 3
6
第一个样例的说明：
因此，最大的 。
翻译由 DeepSeek V3 完成
