← 返回题目列表

AtCoder · ddcc2017_final_c

C. 图形摆弄

中文机器翻译题面 查看原题

配点 : 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 即可。