Description

There are N cities (marked by 1, 2, …, N) and M bidirectional roads in the kingdom. There may be several roads between any two cities, but there is not any road connects the same city.

Your task is to find a shortest path from city 1 to city N, and the lengths of the edges you passed by must be strictly in increasing order.

Input

There is an integer T (1 <= T <= 500) in the first line, indicates that there are T test cases in total.

For each test case, there are two integers N (2 <= N <= 10000) and M (1 <= M <= 50000), which have the same meaning as above. Then there are M lines, and there are three integers x (1 <= x <= N), y (1 <= y <= N), and z (1 <= z <= 10000000) in each line, indicate there is a bidirectional road between city x and city y.

There are at most ten test cases that satisfy that N > 200 or M > 1000.

Output

For each test case, you should output the length of the shortest path you find in the above task. 　　 If such path does not exist, you should just output “No answer” (without quotation mark) instead.

4
4 6
1 2 1
1 2 2
2 3 3
2 3 1
3 4 2
4 3 6
3 2
1 2 1
2 3 1
3 1
1 2 1
2 2
2 1 1
1 2 2

10
No answer
No answer
1