小z放假了，准备到RRR城市旅行，其中这个城市有N个旅游景点。小z时间有限，只能在三个旅行景点进行游玩。小明租了辆车，司机很善良，说咱不计路程，只要你一次性缴费足够，我就带你走遍RRR城。 小z很开心，直接就把钱一次性缴足了。然而小z心机很重，他想选择的路程尽量长。 然而司机也很聪明，他每次从一个点走到另外一个点的时候都走最短路径。 你能帮帮小z吗？ 需要保证这三个旅行景点一个作为起点，一个作为中转点一个作为终点。（一共三个景点，并且需要保证这三个景点不能重复）.

本题包含多组输入，第一行输入一个整数 \( t \)，表示测试数据的组数。 每组测试数据第一行输入两个数 \( N, M \)，表示 RRR 城一共有的旅游景点的数量，以及 RRR 城中有的路的数量。 接下来 \( M \) 行，每行三个数 \( a, b, c \)，表示从 \( a \) 景点和 \( b \) 景点之间有一条长为 \( c \) 的路（可能会有重边，但不会有自环）。 - \( t \le 40 \) - \( 3 \le N, M \le 1000 \) - \( 1 \le a, b \le N \) - \( 1 \le c \le 100 \)

每组数据包含一行，输出一个数，表示整条路程的路长。 如果找不到可行解，输出-1.

请注意这是一个稀疏图.

牛客2021秋季算法入门班第九章习题：图论