配点 : $400$ 点

問題文

$x$ 軸上に $N$ 人の人が立っています。 人 $i$ の位置を $x_i$ とします。 任意の $i$ に対して、$x_i$ は $0$ 以上 $10^9$ 以下の整数です。 同じ位置に複数の人が立っていることもありえます。

これらの人の位置に関する情報が $M$ 個与えられます。 このうち $i$ 個めの情報は $(L_i, R_i, D_i)$ という形をしています。 この情報は、人 $R_i$ は人 $L_i$ よりも距離 $D_i$ だけ右にいること、 すなわち、$x_{R_i} - x_{L_i} = D_i$ が成り立つことを表します。

これら $M$ 個の情報のうちのいくつかに誤りがある可能性があることがわかりました。 与えられる $M$ 個すべての情報と矛盾しないような値の組 $(x_1, x_2, ..., x_N)$ が存在するかどうか判定してください。

制約

• $1 \leq N \leq 100,000$
• $0 \leq M \leq 200,000$
• $1 \leq L_i, R_i \leq N$ ($1 \leq i \leq M$)
• $0 \leq D_i \leq 10,000$ ($1 \leq i \leq M$)
• $L_i \neq R_i$ ($1 \leq i \leq M$)
• $i \neq j$ のとき、$(L_i, R_i) \neq (L_j, R_j)$ かつ $(L_i, R_i) \neq (R_j, L_j)$
• $D_i$ は整数である

入力

入力は以下の形式で標準入力から与えられる。

$N$ $M$

$L_1$ $R_1$ $D_1$

$L_2$ $R_2$ $D_2$

$:$

$L_M$ $R_M$ $D_M$

出力

与えられるすべての情報と矛盾しない値の組 $(x_1, x_2, ..., x_N)$ が存在するときは Yes と、存在しないときは No と出力せよ。

3 3
1 2 1
2 3 1
1 3 2

Yes

値の組 $(x_1, x_2, x_3)$ として、$(0, 1, 2)$ や $(101, 102, 103)$ などが考えられます。

3 3
1 2 1
2 3 1
1 3 5

No

はじめの $2$ つの情報が正しいとすると、$x_3 - x_1 = 2$ が成り立つことが分かります。 これは最後の情報に矛盾します。

4 3
2 1 1
2 3 5
3 4 2

Yes

10 3
8 7 100
7 9 100
9 8 100

No

100 0

Yes