Given a weighted directed graph with N nodes (numbered from 1 to N), find the length of the shortest path from node 1 to node N.

If it can be arbitrarily small, output "negative infinity" (without quotes).

If no path exists, output "unreachable" (without quotes).

Otherwise output the length of the shortest path.

Input

The first line of input contains two integers, N and M. (1 ≤ N ≤ 300, 0 ≤ M ≤ 10000)

The next M lines of input contain the edges of the graph.

The (i + 1)-th line contains three integers a_i, b_i, c_i (1 ≤ a_i, b_i ≤ N, -1000 ≤ c_i ≤ 1000)

Output

The first and only line of output should contain the string "negative infinity" (without quotes) if the path can be arbitrarily short, "unreachable" (without quotes) (if there is no path between nodes 1 and N), or a number representing the length of the shortest path between 1 and N otherwise.

Example

Input:
3 3
2 3 1
1 3 3
3 3
1 2 1
2 3 1
1 3 3

Output:
2

Input:
4 3
1 2 1
2 3 1
1 3 3

Output:
unreachable

Input:
5 5
1 2 100
2 3 -1
3 4 10
4 2 -10
3 5 100

Output:
negative infinity