AT_pakencamp_2023_day1_h Winter Road

パ研王国には $ 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 $ に移動するとき、かかる時間の最小値を求めてください。 ただし、村 $ 1 $ から村 $ N $ まで道路を何本か使い到達できることは保証されます。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ A_1 $ $ B_1 $ $ C_1 $ $ A_2 $ $ B_2 $ $ C_2 $ $ \vdots $ $ A_M $ $ B_M $ $ C_M $

単位を分として、かかる時間の最小値を出力せよ。

### Sample Explanation 1 村 $ 1 $ から直接村 $ 3 $ に行くと、かかる時間は $ 1 $ 分ですが氷の道を必ず通ることとなります 。 しかし、村 $ 2 $ を経由することで氷の道を通らず村 $ 3 $ に行くことができます。この場合パケン君は村 $ 1 $ で $ 3 $ 分待機する必要があります。 ### Constraints - $ 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 $ まで道路を何本か使い到達できる