#描述#
Lily is an acmer. He lives in XIYUAN. But the training room of zjutacm is in JianXing building. One day, while he is training in JianXing, His girl friend QJJ calls him back to XIYUAN. Because the thing is very very urgent, lily must go back to XIYUAN in mini minutes.
Here is your task. Given the map of the campus, you will calculate the mini minutes that lily has to spend to go back to XIYUAN.

#格式#
##输入格式##
The first line of input contains a integer k, meaning there are k test cases followed.
For each test case, the first line contains two numbers：n, m.
n means there are n import points in our campus. m means there are m roads connecting these import points.
Then there are m lines. Each line contains three integer a, b, c. It means it will take t minutes to go from import point a to import point b or go from import point b to import point a.
Be careful: (0&ltk&lt10, 0&ltn&lt1000, 0&ltm&ltn*n/2, 0&ltt&lt1000,0&lta,b&ltn).
The JianXing is at import point 1 and XIYUAN is at import point n.

##输出格式##
For each test case ,output an number one line representing the mini minutes lily can spend to go back to XIYUAN from JianXing. If lily can not go back to XIYUAN, please output -1.

#样例1#
##样例输入1##

1
5 5
1 2 20
2 3 30
3 4 20
4 5 20
1 5 100

##样例输出1##

90

#限制#
1000ms
32768KB

#提示#

#来源#
lily