Systems of difference constraints P23267

A system of difference constraints is a set of inequations of the kind $x - y \le 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 \le 4, x_2 - x_3 \le -1, x_3 - x_1 \le -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, \dots, 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 \ne j$, for the inequation $x_i - x_j \le k$. Assume $1 \le n \le 10^3$, $0 \le m \le 5n$, $-10^5 \le k \le 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.