080 - Difference Optimization 2 Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 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 を出力します。