A weighted directed graph is given. It is necessary to find the minimum number of phases with relaxations in the work of the Ford-Bellman algorithm when finding the shortest path from the vertex 1.
Input
The program receives as input one number, the number of vertices n (2 ≤ n ≤ 100) and the number of edges m (2 ≤m ≤ 10 000). The next m lines contain three numbers: a, b and c, where a and b – the beginning of the edge and its end, and c – edge weight (1 ≤ a, b ≤ n, 1 ≤ c ≤ 10,000).
Output
The program should print a single integer - the minimum number of relaxations in the work of the Ford-Bellman algorithm when finding the shortest path from the vertex 1.
|
Enter |
Output |
|
4 3
1 2 1
|
1 |
|
4 3
|
2 |
(c) Shaldin V., 2017