C - グラフいじり

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 800

問題文

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)修正しました

サイクルの長さとは、選んだ辺たちの長さの総和の事を指します。

制約

  • 入力は全て整数
  • 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 へのパスが存在する

入力

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

N M
a_1 b_1 c_1
a_2 b_2 c_2
:
a_M b_M c_M

出力

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


入力例 1

3 3
1 2 1
2 3 2
3 1 3

出力例 1

Yes

どれかの辺の長さを 1+2+3 = 6 減らせばよいです。


入力例 2

4 5
1 2 1
2 3 2
3 1 2
2 4 3
4 1 3

出力例 2

No

入力例 3

4 5
1 2 1
2 3 -2
3 1 2
2 4 -3
4 1 3

出力例 3

Yes

1 番目の辺の長さを 0 にすればよいです。