AT_ddcc2017_final_c グラフいじり

[problemUrl]: https://atcoder.jp/contests/ddcc2017-final/tasks/ddcc2017_final_c $ N $ 頂点 $ M $ 辺の有向グラフが与えられます。 頂点には $ 1,\ 2,\ ...,\ N $ と番号が付いており、 $ i $ 番目の辺は頂点 $ a_i $ から頂点 $ b_i $ へ張られる、長さ $ c_i $ の辺です。 また、このグラフは**強連結**、つまりすべての $ i,\ j(1\ ≦\ i,\ j\ ≦\ N) $ について、 頂点 $ i $ から頂点 $ j $ へのパスが存在します。 あなたはこのグラフの辺を $ 1 $ 本だけ選び、長さを好きに変える事が出来ます。 なお、元の長さと同じ長さにしても良いです。 グラフを、どのサイクルを選んでも長さが $ 0 $ となるようにできるかを判定してください。 グラフから $ 2 $ 本以上辺を選んだ時(辺を $ M $ 本、$ d_1,\ d_2,\ ...,\ d_M $ 番目の辺を選んだとします)、以下の条件を満たすならば、この選んだ辺たちをグラフのサイクルと呼びます。 - $ i\ =\ 1,\ 2,\ ...,\ M-1 $ について、$ b_{d_i}\ =\ a_{d_{i+1}} $ - $ a_{d_1}\ =\ b_{d_M} $ (11:26)修正しました - $ i\ ≠\ j $ ならば、$ a_{d_i}\ ≠\ a_{d_j} $ (11:22)修正しました サイクルの長さとは、選んだ辺たちの長さの総和の事を指します。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ a_1 $ $ b_1 $ $ c_1 $ $ a_2 $ $ b_2 $ $ c_2 $ $ : $ $ a_M $ $ b_M $ $ c_M $

グラフを、どのサイクルを選んでも長さが $ 0 $ となるようにできるならば `Yes`、できないならば `No` と出力してください。

### 制約 - 入力は全て整数 - $ 2\ ≦\ N\ ≦\ 300 $ - $ 1\ ≦\ M\ ≦\ N^2\ -\ N $ - $ 1\ ≦\ a_i,\ b_i\ ≦\ N $ - $ |c_i|\ ≦\ 10^9 $ - $ a_i\ ≠\ b_i $ - すべての $ 1\ ≦\ i,\ j\ ≦\ M $ について、$ i\ ≠\ j $ ならば $ a_i\ ≠\ a_j $ もしくは $ b_i\ ≠\ b_j $ - 与えられるグラフは強連結、つまりすべての $ 1\ ≦\ i,\ j\ ≦\ N $ について、頂点 $ i $ から頂点 $ j $ へのパスが存在する ### Sample Explanation 1 どれかの辺の長さを $ 1+2+3\ =\ 6 $ 減らせばよいです。 ### Sample Explanation 3 $ 1 $ 番目の辺の長さを $ 0 $ にすればよいです。