1396_最难的工作

真的很难：求 12345678987654321! 里面0的个数，其中!是阶乘。

好吧，我是开玩笑的。地球上还没人能解决这个问题。

实际上，你是一个间谍，从敌人那里偷了一些机密，现在你需要找一条最快离开的路。

路有很多条，交汇点也有很多个，而且两个交汇点之间还可能不止一条路。

你很迷惑，但是你有手机！

你会不会用手机编程呢？

你不会告诉我说你不会用手机编程吧？

你不是真的不会用手机编程吧？

好吧你真的不会用手机编程。。。

第一行是一个整数T ( T ≤ 100 )，表示测试用例的个数。

每个测试用例的第一行是两个整数 n 和 m ( 1 ≤ n ≤ 200 , 0 ≤ m ≤ 10000 )，分别表示交汇点的个数以及路的条数。接下来的m行都有3个整数 i, j, k ( i ≠ j, 1 ≤ k ≤ 10000 )，表示在城市i 和城市j 之间有一条长度为k的路。

假设交汇点从1到n编号。你的出发点是1，目的地是n。

道路都是双向的。

每个测试用例输出一行，一个整数：逃跑的最短距离。如果无路可逃，输出-1。

1
2 1
1 2 3

3