Negcycle. negative cycle
Problem
A weighted directed graph is given. It is required to determine whether it contains a cycle of negative weight. It is guaranteed that all vertices of the graph are reachable from the first one.
Input:
The first line of the input file contains two natural numbers n and m — the number of vertices and edges of the graph respectively ( n ≤ 1 111, m ≤ 11 111).
The next m lines contain the description of the edges, one per line. Edge number i is described by three numbers bi, ei and wi — the numbers of the ends of the rib and its weight, respectively (1 ≤ bi, ei ≤ n, −100 000 ≤ wi ≤ 100 000). Note that the graph can have multiple edges and loops.
Output:
The first line of the output file should contain yes if the graph contains a cycle of negative weight and no — otherwise.
Examples
| # |
Input |
Output |
| 1 |
4 4
2 1-4
1 2 1
3 4 2
2 3 3
| yes |
| 2 |
4 6
2 1 4
1 2 1
3 4 2
2 3 3
1 1 2
1 2 2
| no |