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* ≤ 5*n*,
−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++
- Event
- Tretzè Concurs de Programació de la UPC - Final
- Date
- 2015-09-16