SP1465 CHRIS - On the Way to Find Chris

你是否玩过著名的游戏《拳皇》？如果玩过，我想你一定知道「黑三」组合：Chris、Shermie和Yashiro。今天，Chris受邀去朋友家玩，而Blue Mary此时正待在Chris的家中。虽然Mary知道Shermie和Yashiro的家在哪里，但她并不确定Chris此时究竟在哪里。因此，她计划如下： - 如果Yashiro的家离Chris的家比Shermie的家更近，她会先去Yashiro的家；如果在那里找不到Chris，再前往Shermie的家。反之亦然。 - 这座城市的地图相当特别。每个房子都有一个独一无二的编号，编号范围为\[1, n\]，其中$n$代表房子的总数。某些房子之间有道路连接，可以保证从任意一所房子到任何其他房子之间只有一条路径。她会沿着这条唯一路径前行。

第一行给出测试用例的数量$T$。接下来有$T$组测试数据。 对于每个测试用例，第一行包含两个用空格分隔的整数$N$和$M$，分别表示城市中房子的数量和道路的数量。接下来的$M$行每行包含三个用空格分隔的整数$x$、$y$和$z$，表示在编号为$x$和$y$的房子之间有一条道路，沿此道路从$x$到$y$或从$y$到$x$都需要$z$分钟。确保每条道路都是唯一的。

对于每个测试用例，你需要输出一个整数，代表所需的最大时间（以分钟为单位）。

- 房子数量$N$满足$3 \le N \le 200000$ - 测试用例数量满足$1 \le T \le 10$ **本翻译由 AI 自动生成**