题目描述

给你一个包含 $n$ 个顶点 $m$ 条有向边的有向图。

判断图中是否存在负环。

输入格式

第一行，两个整数 $n$ 和 $m$，以一个空格分隔（$1 \le n \le 2000, 1 \le m \le 5000$）。

接下来 $m$ 行，每行包含三个整数 $u, v, w$，以空格分隔，表示存在一条从顶点 $u$ 出发到达顶点 $v$ 的权值为 $w$ 的有向边（$1 \le u,v \le n, u \neq v, -1000 \le w \le 1000$）。

输出格式

如果图中存在负环，输出 YES；否则，输出 NO。

样例

3 3
1 2 3
2 3 -2
3 1 -2

YES

3 5
1 2 3
1 3 5
2 3 6
3 1 -3
3 2 -4

NO