問題文

パ研王国には N 個の村と M 本の道路があります。 i\ (1 \le i \le M) 本目の道路は村 A_i, B_i を双方向に結んでいて、どの状態であっても渡るのに 1 分かかります。

最初、すべての道路に氷が張ってあります。 C_i = -1 の場合は氷はとけず、 1 \le C_i の場合、 C_i 分後に氷がとけます。

国王であるパケン君は最初村 1 にいて、道路を何本か通ることで村 N まで移動したいです。パケン君は任意の村で待機することもできます。また、パケン君は用心深いため、氷の張ってある道をなるべく通りたくないです。氷の張ってある道を通る時間を最小化して街 N に移動するとき、かかる時間の最小値を求めてください。

制約

• 2 \leq N \leq 2\times 10^5
• N-1 \leq M \leq \min(\frac{N(N-1)}{2} , 2\times 10^5)
• 1 \le A_i < B_i \le N
• 1 \le i < j \le N について、 (A_i,B_i)\neq (A_j,B_j)
• C_i=-1 または 1 \le C_i \le 10^9
• 入力は全て整数
• 村 1 から村 N まで道路を何本か使い到達できる

入力例 1

3 3
1 3 -1
1 2 3
2 3 1

出力例 1

5

村 1 から直接村 3 に行くと、かかる時間は 1 分ですが氷の道を必ず通ることとなります 。 しかし、村 2 を経由することで氷の道を通らず村 3 に行くことができます。この場合パケン君は村 1 で 3 分待機する必要があります。

入力例 2

4 5
1 2 1
2 4 -1
1 3 -1
3 4 3
2 3 3

出力例 2

5