/ 
Time Limit: 3 sec / Memory Limit: 256 MB
配点 : 600 点
問題文
すぬけ君の住んでいる街には地下鉄が走っています。駅は全部で N 個あり、路線は全部で M 本あります。 駅には 1 から N までの整数が付けられています。また、それぞれの路線はある 1 つの会社によって運営されており、 それぞれの会社には会社をあらわす整数がつけられています。
i 番目 ( 1 \leq i \leq M ) の路線は、駅 p_i と 駅 q_i を相互に結んでいます。途中に他の駅はありません。 また、この路線は会社 c_i によって運営されています。 同じ駅を通る路線が複数あるときは、その駅で乗り換えることができます。
それぞれの会社について、同じ会社の路線を使い続ける限り料金は 1 ですが、別の会社の路線に乗り換えるたびに新たに料金が 1 かかります。 ある会社を利用し、別の会社を利用してからまた最初の会社を利用する場合でも、再び料金を払う必要があります。
すぬけ君は、駅 1 を出発し、地下鉄を利用して駅 N に行きたいです。移動にかかる料金の最小値を求めてください。
制約
- 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)
入力
入力は以下の形式で標準入力から与えられる。
N M p_1 q_1 c_1 : p_M q_M c_M
出力
移動にかかる料金の最小値を出力せよ。すぬけ君が駅 N に到達することが不可能な場合には、代わりに -1 を出力せよ。
入力例 1
3 3 1 2 1 2 3 1 3 1 2
出力例 1
1
1 → 2 → 3 と会社 1 の路線を使って移動することができ、この場合必要なコストは 1 です。
入力例 2
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
1 → 3 → 2 → 5 → 6 と会社 1 の路線を利用し、その後 6 → 7 → 8 と会社 5 の路線を利用することで、コスト 2 で目的地に到達できます。
入力例 3
2 0
出力例 3
-1
Score : 600 points
Problem Statement
Snuke's town has a subway system, consisting of N stations and M railway lines. The stations are numbered 1 through N. Each line is operated by a company. Each company has an identification number.
The i-th ( 1 \leq i \leq M ) line connects station p_i and q_i bidirectionally. There is no intermediate station. This line is operated by company c_i.
You can change trains at a station where multiple lines are available.
The fare system used in this subway system is a bit strange. When a passenger only uses lines that are operated by the same company, the fare is 1 yen (the currency of Japan). Whenever a passenger changes to a line that is operated by a different company from the current line, the passenger is charged an additional fare of 1 yen. In a case where a passenger who changed from some company A's line to another company's line changes to company A's line again, the additional fare is incurred again.
Snuke is now at station 1 and wants to travel to station N by subway. Find the minimum required fare.
Constraints
- 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)
Input
The input is given from Standard Input in the following format:
N M p_1 q_1 c_1 : p_M q_M c_M
Output
Print the minimum required fare. If it is impossible to get to station N by subway, print -1 instead.
Sample Input 1
3 3 1 2 1 2 3 1 3 1 2
Sample Output 1
1
Use company 1's lines: 1 → 2 → 3. The fare is 1 yen.
Sample Input 2
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
Sample Output 2
2
First, use company 1's lines: 1 → 3 → 2 → 5 → 6. Then, use company 5's lines: 6 → 7 → 8. The fare is 2 yen.
Sample Input 3
2 0
Sample Output 3
-1