AT_utpc2024_m Minimum Distance Tree

頂点に $ 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 $ 最短経路長に等しいようなものが存在するか判定してください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ u_1 $ $ v_1 $ $ w_1 $ $ u_2 $ $ v_2 $ $ w_2 $ $ \vdots $ $ u_M $ $ v_M $ $ w_M $

上記のような $ T $ が存在する場合は `Yes` を、存在しない場合は `No` を出力せよ。

### Sample Explanation 1 $ T $ として、頂点 $ 1,2 $ 間に重み $ 3 $ の辺、頂点 $ 2,3 $ 間に重み $ 4 $ の辺がある $ 3 $ 頂点の木が条件を満たします。 ### Sample Explanation 2 条件を満たす $ T $ は存在しません。例えば、頂点 $ 1,2 $ 間に重み $ 2 $ の辺、頂点 $ 1,3 $ 間に重み $ 2 $ の辺がある $ 3 $ 頂点の木は、 $ G $ 上での $ 1 $ - $ 2 $ 最短経路長が $ 3 $ であるのに対して、この木上での $ 1 $ - $ 2 $ 最短経路長が $ 2 $ であり等しくないため条件を満たしません。 ### Constraints - 入力は全て整数 - $ 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 $ - 与えられるグラフは単純かつ連結