問題文

頂点に 1 から N の番号がついた N 頂点 M 辺からなる重み付き単純連結無向グラフ G があります。 i 番目の辺は頂点 u_i,v_i を結ぶ重み w_i の辺です。

頂点に 1 から N の番号がついた N 頂点の重み付き木 T であって、任意の 2 頂点 u,v に対し、 G 上の u-v 最短経路長が T 上の u-v 最短経路長に等しいようなものが存在するか判定してください。

制約

• 入力は全て整数
• 2 \leq N \leq 5 \times 10^5
• N-1 \leq M \leq 5 \times 10^5
• 1 \leq u_i, v_i \leq N
• 1 \leq w_i \leq 10^9
• 与えられるグラフは単純かつ連結

入力例 1

3 3
1 2 3
2 3 4
3 1 100

出力例 1

Yes

T として、頂点 1,2 間に重み 3 の辺、頂点 2,3 間に重み 4 の辺がある 3 頂点の木が条件を満たします。

入力例 2

3 3
1 2 3
2 3 4
3 1 2

出力例 2

No

条件を満たす T は存在しません。例えば、頂点 1,2 間に重み 2 の辺、頂点 1,3 間に重み 2 の辺がある 3 頂点の木は、G 上での 1-2 最短経路長が 3 であるのに対して、この木上での 1-2 最短経路長が 2 であり等しくないため条件を満たしません。