Task
Time limit:
1000 ms,
Memory limit:
32 Mb
Negcycle. Отрицательный цикл
Дан взвешенный ориентированный граф. Требуется определить, содержит ли он цикл отрицательного веса. Гарантируется, что все вершины графа достижимы из первой.
Формат входных данных
Первая строка входного файла содержит два натуральных числа
n и
m — количество вершин и ребер графа соответственно (
n ≤ 1 111,
m ≤ 11 111).
Следующие
m строк содержат описание ребер по одному на строке. Ребро номер
i описывается тремя числами
bi,
ei и
wi — номера концов ребра и его вес соответственно (1 ≤
bi,
ei ≤
n, −100 000 ≤
wi ≤ 100 000). Обратите внимание, что в графе могут быть кратные ребра и петли.
Формат выходных данных
Первая строка выходного файла должна содержать yes, если граф содержит цикл отрицательного веса и no — в противном случае.
Примеры
входные данные
4 4
2 1 -4
1 2 1
3 4 2
2 3 3
входные данные
4 6
2 1 4
1 2 1
3 4 2
2 3 3
1 1 2
1 2 2