比赛场次	181
比赛名称	20121107
比赛状态	已结束比赛成绩
开始时间	2012-11-07 08:15:00
结束时间	2012-11-07 12:00:00
开放分组	全部用户
注释介绍

题目名称	最难的任务
输入输出	`hardest.in/out`
时间限制	1000 ms (1 s)
内存限制	128 MiB
测试点数	5 简单对比

用户	结果	时间	内存	得分
TBK	AAAAA	0.074 s	7.27 MiB	100
as	AAAAA	0.081 s	40.87 MiB	100
RoyJames	AAAAA	0.085 s	0.43 MiB	100
张来风飘	AAAAA	0.091 s	0.32 MiB	100
Vow Ryan	AAAAA	0.091 s	0.79 MiB	100
亟隐	AAAAA	0.092 s	0.41 MiB	100
Sweet	AAAAA	0.094 s	3.98 MiB	100
xm1994	AAAAA	0.098 s	3.15 MiB	100
剑舞江南	AAAAA	0.144 s	1.92 MiB	100
feng	AAAAA	0.167 s	16.25 MiB	100
Cloud	AAAAA	0.176 s	3.30 MiB	100
苏轼	AAAAA	0.260 s	3.28 MiB	100
QhelDIV	AAAAA	0.832 s	3.47 MiB	100
Makazeu	AAAAA	0.833 s	2.13 MiB	100
临轩听雨ゐ	AAAAA	1.460 s	3.30 MiB	100
王者自由	AAAAA	1.675 s	1.70 MiB	100
digital-T	AAAAA	2.273 s	0.24 MiB	100
怡红公子	AAAAA	2.428 s	3.44 MiB	100
Abel·S	AAEEE	0.015 s	0.70 MiB	40
luschegde	AAWWW	0.086 s	0.53 MiB	40
warrior	AAWWW	0.087 s	0.89 MiB	40
CAX_CPG	AAWWW	0.182 s	8.03 MiB	40
limitation	AAWWW	0.738 s	0.51 MiB	40
日光。	AAWWW	0.837 s	2.43 MiB	40
DMC_DY	AATTT	3.001 s	0.42 MiB	40
极寒之魇	EAEWE	0.057 s	3.98 MiB	20
duwei	WAWWW	0.100 s	8.03 MiB	20
bw	WAWWW	0.105 s	0.93 MiB	20
Truth.Cirno	WAWWW	0.239 s	3.62 MiB	20
ZYHAzwraith	AWWWW	0.568 s	3.31 MiB	20
song	WAWWW	1.028 s	3.30 MiB	20
苏轼	AWWWW	1.442 s	3.43 MiB	20
ACdog	AWTET	2.070 s	2.19 MiB	20
FrCsKOH	WATTT	3.000 s	0.47 MiB	20
skyfisherman	C	0.000 s	0.00 MiB	0
awai	C	0.000 s	0.00 MiB	0
馒头	RRRRR	0.001 s	0.58 MiB	0
Lyre	EEEEE	0.001 s	2.08 MiB	0
o_o	EWEEE	0.297 s	0.70 MiB	0
乔治文	WWWWW	0.855 s	0.32 MiB	0
Galaxy无名	WWWWW	0.890 s	2.11 MiB	0

最难的任务

★ 输入文件：hardest.in 输出文件：hardest.out 简单对比
时间限制：1 s 内存限制：128 MiB

【题目描述】

这个真的很难。算出 12345678987654321！，这个“！”是阶乘的意思。

呵，我在开玩笑。没有人成功的解决。

事实上，你是一个间谍。你要窃取一些敌军机密，现在你需要找到一个方法使你逃走的时间最少。

这里有很多交叉点和很多道路，在两个交叉点间可能有多条路。你很困惑，但随身携带笔记本电脑让你很快乐。

【输入格式】

第一行有一个整数T（T≤10）表示测试数据个数。

每组数据以两个整数开始，n和m(1≤n≤200，0≤m≤10000)，交叉点的个数和各自的道路数。下面m行有三个整数 i,j,k(i<>j, 1≤k≤10000), 意思是i和j中间有一条长度为k的路。

你可以假设交叉点的编号为1...n。你需要从交叉点1到交叉点n。

道路是双向的。

【输出格式】

对于每组测试数据，打印最短距离。如果没有路可以出去，打印-1。

【样例输入】

1
2 1
1 2 3

【样例输出】