Дан взвешенный ориентированный граф. Требуется определить, содержит ли он цикл отрицательного веса. Гарантируется, что все вершины графа достижимы из первой.
Входные данные:
Первая строка входного файла содержит два натуральных числа n и m — количество вершин и ребер графа соответственно ( n ≤ 1 111, m ≤ 11 111).
Следующие m строк содержат описание ребер по одному на строке. Ребро номер i описывается тремя числами bi, ei и wi — номера концов ребра и его вес соответственно (1 ≤ bi, ei ≤ n, −100 000 ≤ wi ≤ 100 000). Обратите внимание, что в графе могут быть кратные ребра и петли.
Выходные данные:
Первая строка выходного файла должна содержать yes, если граф содержит цикл отрицательного веса и no — в противном случае.
Примеры
| № |
Входные данные |
Выходные данные |
| 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 |