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