AtCoder Regular Contest 061

E - すぬけ君の地下鉄旅行 / Snuke's Subway Trip


Time limit時間制限 : 3sec / Memory limitメモリ制限 : 256MB

配点 : 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

123 と会社 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

13256 と会社 1 の路線を利用し、その後 678 と会社 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: 123. 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: 13256. Then, use company 5's lines: 678. The fare is 2 yen.


Sample Input 3

2 0

Sample Output 3

-1

Submit提出する