Problem D: One-Time Path

Problem

N個の島とM本の橋がある。 N個の島にはそれぞれ1からNまでの番号が割り振られている。 M本の橋にもそれぞれ1からMまでの番号が割り振られている。

がっちょ君は現在(時刻0の時点で)、1番目の島にいる。 がっちょ君はi番目の橋を利用することにより、a_i番目の島からb_i番目の島へと単方向に移動することができる。

しかし、時刻0の時点では、すべての橋は潮が満ちていて海の中に沈んでしまっている。 i番目の橋は、時刻c_iになると潮が引いて渡れるようになる。 そして、時刻c_iを過ぎると、すぐにまた潮が満ちてi番目の橋は再び沈んでしまう。 再び沈んでしまうと、またいつ潮が引いて渡れるようになるかはわからない。 そこで、がっちょ君はそうなった橋は永遠に渡れなくなると考えるようにした。

がっちょ君は、できるだけ長い間、1からN-1番目の島の景色を眺めていたいのだが、N番目の島に船を泊めてあるので、最終的にはN番目の島に到着していなければならない。また、船の中で両親を待たせているため、がっちょ君はN番目の島についたらすぐに船で出発して家へと帰らなければならない。

がっちょ君が橋を渡ったり島の中を移動する時間はとても短いので、0と仮定してよい。がっちょ君が1からN-1番目のいずれかの島にいることのできる時間の最大値を求めよ。ただし、どのように移動してもがっちょ君がN番目の島へと移動できない場合は代わりに-1を出力せよ。

Input

入力は以下の形式で与えられる。

N M
a1 b1 c1
a2 b2 c2
…
aM bM cM

1行目には、2つの整数N, Mが空白区切りで与えられる。
2行目からM+1行目のそれぞれの行iには、3つの整数a_i, b_i, c_iが空白区切りで与えられる。

Constraints

• 2 ≤ N ≤ 10⁵
• 1 ≤ M ≤ 2 × 10⁵
• 1 ≤ a_i < N
• 1 ≤ b_i ≤ N
• 1 ≤ c_i ≤ 10⁹
• a_i ≠ b_i

Output

がっちょ君がN番目の島へと移動できる場合は、がっちょ君が1からN-1番目のいずれかの島にいることのできる時間の最大値を出力する。N番目の島へと移動できない場合は、代わりに-1を出力する。

Sample Input 1

3 2
1 2 10
2 3 20

Sample Output 1

20

まず、1番目の島で時刻が10になるまで待ってから、2番目の島へと移動する。
次に、2番目の島で時刻が20になるまで待ってから、3番目の島へと移動する。
以上より、1から2番目のいずれかの島にいる時間は20となる。

Sample Input 2

4 4
1 2 27
1 3 37
2 3 47
3 1 57

Sample Output 2

-1

4番目の島に繋がる橋がないため、4番目の島へ移動することができない。

Sample Input 3

3 3
1 2 13
2 3 17
2 3 15

Sample Output 3

17

Sample Input 4

3 2
1 2 20
2 3 10

Sample Output 4

-1

Sample Input 5

3 2
1 2 10
2 3 10

Sample Output 5

10

Note

Link

 

---