Systems of difference constraints P23267


Statement
 

pdf   zip

thehtml

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 { x1 − x2 ≤ 4, x2 − x3 ≤ −1, x3 − x1 ≤ −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 i ≠ j, for the inequation xi − xj ≤ k. Assume 1 ≤ n ≤ 103, 0 ≤ m ≤ 5n, −105 ≤ k ≤ 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++