Time Limit: 1000 MS Memory Limit: 32726 K


Description

每年的双十一,我们都享受着网购的快捷与便利,但是货物如何快速从起始城市运送到目标城市就成了一个头疼的问题。你能帮帮快递公司吗?

Input

输入包含多个输入用例,输入的第一行为测试用例的数量。每个测试用例的第一行是两个整数n和m(n100, m10000),n表示共有几个城市,标号为1的城市是货物的始发地,标号为n的城市是货物的目的地,m则表示在这几个城市间共有几条道路。接下来的m行,每行包括3个整数A, B, C(1A, BN, 1C1000),表示在城市A和城市B之间有一条道路,而货车需要C小时的时间走过这条路。输入保证至少存在1条从始发地到目的地的道路。

Output

每个测试样例输出一行,表示货车从始发地到目的地花费的最短时间。

Sample Input

1
3 3
1 2 5
2 3 5
3 1 2

Sample Output

2