Systems of difference constraints P23267

Statement

thehtml

A system of difference constraints is a set of inequations of the kind xyk, 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 { x1x2 ≤ 4, x2x3 ≤ −1, x3x1 ≤ −2 } has, among other solutions, x1 = 4, x2 = 0 and x3 = 2.

Write a program that, given a system of difference constraints with n variables x1, …, xn 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 ij, for the inequation xixjk. Assume 1 ≤ n ≤ 103, 0 ≤ m ≤ 5n, −105k ≤ 105, 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++