← 返回题目列表

AtCoder · math_and_algorithm_bl

080. 差异优化2

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

配点: 1000 点

問題文

整数 x_1,x_2,\dots,x_N 满足以下所有条件: 关于

  • x_1=0 。
  • 1 \le i \le M , 当我输入|x_{A_i}-x_{B_i}| \le C_i 很满意。

x_N 的最大可能值。 如果

制約

  • 2 \leq N \leq 100000
  • 0 \leq M \leq 500000
  • 1 \leq A_i < B_i \leq N
  • 0 \leq C_i \leq 10^9
  • 所有输入均为整数

入力

输入是按以下格式从标准输入给出的。

N M
A_1 B_1 C_1
A_2 B_2 C_2
:
A_M B_M C_M

出力

x_N 可以任意大,那么-1 。 输出

如果没有, 请输出x_N 的最大值。


入力例 1

4 4
1 2 3
1 3 4
3 4 1
2 4 10

出力例 1

5

x_1=0,x_2=3,x_3=4,x_4=5 ,x_4 是最大值 5 。 对于


入力例 2

2 0

出力例 2

-1

x_2 可以任意大,所以 输出-1 。