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