题目描述

すぬけ君の住んでいる街には地下鉄が走っています。駅は全部で $N$ 個あり、路線は全部で $M$ 本あります。 駅には $1$ から $N$ までの整数が付けられています。また、それぞれの路線はある $1$ つの会社によって運営されており、 それぞれの会社には会社をあらわす整数がつけられています。

$i$ 番目 ( $1\ \leq\ i\ \leq\ M$ ) の路線は、駅 $p_i$ と 駅 $q_i$ を相互に結んでいます。途中に他の駅はありません。 また、この路線は会社 $c_i$ によって運営されています。 同じ駅を通る路線が複数あるときは、その駅で乗り換えることができます。

それぞれの会社について、同じ会社の路線を使い続ける限り料金は $1$ ですが、別の会社の路線に乗り換えるたびに新たに料金が $1$ かかります。 ある会社を利用し、別の会社を利用してからまた最初の会社を利用する場合でも、再び料金を払う必要があります。

すぬけ君は、駅 $1$ を出発し、地下鉄を利用して駅 $N$ に行きたいです。移動にかかる料金の最小値を求めてください。

输入格式

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

$N$ $M$ $p_1$ $q_1$ $c_1$ : $p_M$ $q_M$ $c_M$

输出格式

移動にかかる料金の最小値を出力せよ。すぬけ君が駅 $N$ に到達することが不可能な場合には、代わりに -1 を出力せよ。

题目大意

题目描述

Snuke的城镇有地铁行驶，地铁线路图包括 $N$ 个站点和 $M$ 个地铁线。站点被从 $1$ 到 $N$ 的整数所标记，每条线路被一个公司所拥有，并且每个公司用彼此不同的整数来表示。

第 $i$ 条线路( $1≤i≤M$ )是直接连接 $p_i$ 与 $q_i$ 的双向铁路，中间不存在其他站点，且这条铁路由 $c_i$ 公司所拥有。

如果乘客只乘坐同一公司的铁路，他只需要花费一元，但如果更换其他公司的铁路需要再花一元。当然，如果你要再换回原来的公司，你还是要花一元。

Snuke在1号站的位置出发，他想通过地铁去第 $N$ 站，请求出最小钱数。如果无法到达第 $N$ 站，输出-1。

输入输出格式

输入格式

第一行，输入 $N$ , $M$

接下来的 $M$ 行，输入 $p_i$ $q_i$ $c_i$ ，代表 $p_i$ 与 $q_i$ 中间有直接连接的双向边，且这条铁路由 $c_i$ 公司所拥有。

输出格式

输出最小钱数（若无法到达，输出-1）

感谢@SaltedHXJ 提供的翻译

3 3
1 2 1
2 3 1
3 1 2

1

8 11
1 3 1
1 4 2
2 3 1
2 5 1
3 4 3
3 6 3
3 7 3
4 8 4
5 6 1
6 7 5
7 8 5

2

2 0

-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$ で目的地に到達できます。