A *system of difference constraints* is a set of inequations
of the kind x − y ≤ k,
where x and y are integer variables,
and k is an integer constant.
Given a system of difference constraints,
a *solution* is an assignment of values to variables
in such a way that all inequations hold.

For instance, the system of difference constraints
{ x_{1} − x_{2} ≤ 4, x_{2} − x_{3} ≤ −1, x_{3} − x_{1} ≤ −2 }
has, among other solutions, x_{1} = 4, x_{2} = 0 and x_{3} = 2.

Write a program that, given a system of difference constraints
with n variables x_{1}, …, x_{n}
and m inequations among them,
tells if there is some solution or not.

Input

Input consists of several cases.
Every case begins with n and m,
followed m triplets i, j, k, with i ≠ j,
for the inequation x_{i} − x_{j} ≤ k.
Assume 1 ≤ n ≤ 10^{3},
0 ≤ m ≤ 5n,
−10^{5} ≤ k ≤ 10^{5},
and that every pair of i and j appears at most once.
All given numbers are integers.

Output

For every case, print “yes” if the system has some solution, and print “no” otherwise.

Public test cases

**Input**

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

**Output**

yes no yes

Information

- Author
- Enric Rodríguez
- Language
- English
- Official solutions
- C++
- User solutions
- C++