Problem O: 旅游4

Problem O: 旅游4

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 42  Solved: 15
[Submit] [Status] [Web Board] [Creator:]

Description

奥利奥放假了,他到城市A旅游,城市A有N个景点,他时间有限,只能在三个景点游玩。他包了出租车,他很鸡贼,想坐尽量长的路程,但司机也很聪明,在两个景点间,会选择最短的路。旅游景点不能重复,请你帮他求出他能坐的最长路程。

Input

多组输入,第一行输入一个整数t,表示测试数据的组数
每组测试数据第一行输入两个数N,M表示城市A一共有的旅游景点的数量,以及城市A中有的路的数量。
接下来M行,每行三个数,a,b,c表示从a景点和b景点之间有一条长为c的路
t<=40
3<=N,M<=1000
1<=a,b<=N
1<=c<=100

Output

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

Sample Input Copy

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 Output Copy

422
3
-1
9