Отрицательный цикл

1000 мс · 256 МБ · всё или ничего

Определите, есть ли в ориентированном графе цикл отрицательного веса.

Формат ввода

В первой строке $n$ и $m$ ( $1 \le n \le 2000$ , $0 \le m \le 10^4$ ). В каждой из следующих $m$ строк — числа $a_i$ , $b_i$ , $w_i$ ( $|w_i| \le 10^6$ ) — ориентированное ребро.

Формат вывода

Выведите YES, если отрицательный цикл есть, и NO иначе.

Примеры

ввод

1 0

вывод

NO

Разбор идеи от автора задачи. Сначала попробуйте сами.

Войдите, чтобы отправлять решения.