### 问题描述 蓝桥公司招聘了一个推销员。他大部分时间都在不同的城市之间旅行。他决定买一辆新车来帮助他的工作，但他必须决定新车油箱的容量。假设这辆新车每公里耗油一升。 每个城市至少有一个加油站，推销员可以在那里给油箱加油，但城市之间的道路上没有加油站。 给出城市及其之间道路的描述，找出所需油箱的最小容量，以便推销员能够至少以一种方式在任何一对城市之间旅行。 ### 输入格式 输入的第一行包含表示测试用例数的 $T$。 每个测试用例的第一行包含两个整数：$N$ 和 $M$ ，其中 $N$ 为城市数量，$M$ 为道路数量。 以下 $M$ 行都包含三个整数：$X,Y,C$，其中 $C$ 是城市 $X$ 和城市 $Y$ 之间的长度，单位为公里。道路可以双向使用。 题目保证每对城市之间最多有一条道路相连，并且可以使用给定的道路在任意一对城市之间旅行。 ### 输出格式 对于每个测试用例，打印一行整数表示油箱所需的最小容量。 ### 样例输入 ``` 2 6 7 1 2 3 2 3 3 3 1 5 3 4 4 4 5 4 4 6 3 6 5 5 3 3 1 2 1 2 3 2 3 1 3 ``` ### 样例输出 ``` 4 2 ``` ### 评测数据规模 对于 $100$% 的评测数据，$1\leq T \leq 5,3 \leq N \leq 100000, N - 1\leq M \leq 100000,1\leq X,Y\leq N,X\neq Y,1 \leq C \leq 100000$。