最难的任务

【题目描述】

这个真的很难。算出 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

【样例输出】

3