AT_arc061_c [ARC061E] すぬけ君の地下鉄旅行

Snuke的城镇有地铁行驶，地铁线路图包括 $N$ 个站点和 $M$ 个地铁线。站点被从 $1$ 到 $N$ 的整数所标记，每条线路被一个公司所拥有，并且每个公司用彼此不同的整数来表示。 第 $i$ 条线路( $1≤i≤M$ )是直接连接 $p_i$ 与 $q_i$ 的双向铁路，中间不存在其他站点，且这条铁路由 $c_i$ 公司所拥有。 如果乘客只乘坐同一公司的铁路，他只需要花费一元，但如果更换其他公司的铁路需要再花一元。当然，如果你要再换回原来的公司，你还是要花一元。 Snuke在1号站的位置出发，他想通过地铁去第 $N$ 站，请求出最小钱数。如果无法到达第 $N$ 站，输出-1。

无

无

### 制約 - $ 2\ \leq\ N\ \leq\ 10^5 $ - $ 0\ \leq\ M\ \leq\ 2×10^5 $ - $ 1\ \leq\ p_i\ \leq\ N $ $ (1\ \leq\ i\ \leq\ M) $ - $ 1\ \leq\ q_i\ \leq\ N $ $ (1\ \leq\ i\ \leq\ M) $ - $ 1\ \leq\ c_i\ \leq\ 10^6 $ $ (1\ \leq\ i\ \leq\ M) $ - $ p_i\ \neq\ q_i $ $ (1\ \leq\ i\ \leq\ M) $ ### Sample Explanation 1 $ 1 $ → $ 2 $ → $ 3 $ と会社 $ 1 $ の路線を使って移動することができ、この場合必要なコストは $ 1 $ です。 ### Sample Explanation 2 $ 1 $ → $ 3 $ → $ 2 $ → $ 5 $ → $ 6 $ と会社 $ 1 $ の路線を利用し、その後 $ 6 $ → $ 7 $ → $ 8 $ と会社 $ 5 $ の路線を利用することで、コスト $ 2 $ で目的地に到達できます。