← 返回题目列表

AtCoder · arc090_b

D. 排队的人

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

分数: 400 点

问题陈述

有 N 人们站在 x- 轴。 设 Person 的坐标 i be x_i。 对于每一个 i, x_i 是介于 0 和 10^9 (含)。 有可能不止一个人站在同一坐标处。

你将给予 M 有关这些人的职位的信息。 的 i第一条信息具有以下形式 (L_i, R_i, D_i)。 这意味着该人 R_i 位于人的右侧 L_i by D_i 距离单位,即 x_{R_i} - x_{L_i} = D_i 成立。

事实证明,其中一些 M 信息可能不正确。 判断是否存在一组值 (x_1, x_2, ..., x_N) 与给定的信息一致。

约束

  • 1 \leq N \leq 100 000
  • 0 \leq M \leq 200 000
  • 1 \leq L_i, R_i \leq N (1 \leq i \leq M)
  • 0 \leq D_i \leq 10 000 (1 \leq i \leq M)
  • L_i \neq R_i (1 \leq i \leq M)
  • If i \neq j,那么 (L_i, R_i) \neq (L_j, R_j) 和 (L_i, R_i) \neq (R_j, L_j).
  • D_i 是整数。

输入

输入由标准输入按以下格式给出:

N M
L_1 R_1 D_1
L_2 R_2 D_2
:
L_M R_M D_M

输出

如果存在一组值 (x_1, x_2, ..., x_N) 与所有给定的信息一致,打印 Yes;如果不存在,则打印 No.


示例输入 1

3 3
1 2 1
2 3 1
1 3 2

示例输出 1

Yes

一些可能的值集 (x_1, x_2, x_3) 是 (0, 1, 2) 和 (101, 102, 103).


示例输入 2

3 3
1 2 1
2 3 1
1 3 5

示例输出 2

No

如果前两条信息正确, x_3 - x_1 = 2 成立,这与最后一条信息矛盾。


示例输入 3

4 3
2 1 1
2 3 5
3 4 2

示例输出 3

Yes

示例输入 4

10 3
8 7 100
7 9 100
9 8 100

示例输出 4

No

示例输入 5

100 0

示例输出 5

Yes