7430: 旅行
[Creator : ]
Description
小 z 放假了，准备到 R 城市旅行，其中这个城市有 N 个旅游景点。
小 z 时间有限，只能在三个旅行景点进行游玩。小明租了辆车，司机很善良，说咱不计路程，只要你一次性缴费足够，我就带你走遍 R 城。
小 z 很开心，直接就把钱一次性缴足了。然而小 z 心机很重，他想选择的路程尽量长。然而司机也很聪明，他每次从一个点走到另外一个点的时候都走最短路径。
你能帮帮小 z 吗？
需要保证这三个旅行景点一个作为起点，一个作为中转点一个作为终点。（一共三个景点，并且需要保证这三个景点不能重复）.
小 z 时间有限，只能在三个旅行景点进行游玩。小明租了辆车，司机很善良，说咱不计路程，只要你一次性缴费足够，我就带你走遍 R 城。
小 z 很开心，直接就把钱一次性缴足了。然而小 z 心机很重，他想选择的路程尽量长。然而司机也很聪明，他每次从一个点走到另外一个点的时候都走最短路径。
你能帮帮小 z 吗？
需要保证这三个旅行景点一个作为起点，一个作为中转点一个作为终点。（一共三个景点，并且需要保证这三个景点不能重复）.
Input
本题包含多组输入，第一行输入一个整数 t，表示测试数据的组数
每组测试数据第一行输入两个数 N,M。表示 R 城一共有的旅游景点的数量，以及 R 城中有的路的数量。
接下来 M 行，每行三个数，a，b，c。表示从 a 景点和 b 景点之间有一条长为 c 的路
每组测试数据第一行输入两个数 N,M。表示 R 城一共有的旅游景点的数量，以及 R 城中有的路的数量。
接下来 M 行，每行三个数，a，b，c。表示从 a 景点和 b 景点之间有一条长为 c 的路
Output
$t \leq 40$
$3 \leq N,M \leq 1000$
$1 \leq a,b \leq N$
$1 \leq c \leq 100$
$3 \leq N,M \leq 1000$
$1 \leq a,b \leq N$
$1 \leq c \leq 100$
Constraints
每组数据包含一行，输出一个数，表示整条路程的路长。
如果找不到可行解，输出 -1。
如果找不到可行解，输出 -1。
Sample 1 Input
4
7 7
1 2 100
2 3 100
1 4 4
4 5 6
5 6 10
1 6 4
6 7 8
7 3
1 2 1
1 3 1
1 3 2
7 3
1 2 1
3 4 1
5 6 1
8 9
1 2 1
2 3 1
3 4 1
4 1 1
4 5 1
5 6 1
6 7 1
7 8 1
8 5 1
Sample 1 Output
422
3
-1
9