Negative Cycle Check

Statement

You are given a directed graph with n nodes and m edges. Edge i goes from a to b and has a weight w, which may be negative. Decide whether the graph contains a cycle whose total weight is strictly less than zero. The cycle may be anywhere in the graph, not only on routes starting from node 1. Self-loops are allowed.

Input

The first line has n and m. Each of the next m lines has a, b and w.

Output

Print YES if some cycle has negative total weight, otherwise NO.

Constraints

1 <= n <= 500
0 <= m <= 5000
|w| <= 10^6

Example 1

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

YES

The cycle 1, 2, 3, 1 has total weight 4 - 6 + 1 = -1.

Example 2

3 2
1 2 -5
2 3 -5

NO

There are negative edges but no cycle at all.