Problem hidden
This problem was hidden by Editorial Board member probably because it has incorrect language version or invalid test data, or description of the problem is not clear.

Problem hidden

NEGCYC - Negative Cycles

no tags 

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 ai, bi, ci (1 ≤ ai, bi ≤ N, -1000 ≤ ci ≤ 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

Added by:gustav
Date:2014-12-05
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:classical problem