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 32 3 11 3 33 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