D - ネットワーク敷設 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 366 点

問題文

高橋君は通信会社のネットワークエンジニアとして、光ファイバーケーブルの敷設計画を担当しています。

市内には N 個の中継局があり、 1 から N までの番号が付けられています。また、 M 本の地下トンネルがあり、それぞれのトンネルは異なる2つの中継局を双方向に結んでいます。 i 番目のトンネル (1 \leq i \leq M) は中継局 U_i と中継局 V_i を結び、幅は W_i センチメートルです。

高橋君は、中継局 1 にあるデータセンターから中継局 N にある顧客ビルまで、幅 K センチメートルの光ファイバーケーブル束を敷設したいと考えています。ケーブル束をトンネルに通すためには、そのトンネルの幅がケーブル束の幅 K センチメートル以上でなければなりません。したがって、敷設経路上のすべてのトンネルの幅が K センチメートル以上である必要があります。

ここで、中継局 1 から中継局 N への経路とは、中継局の列 v_0, v_1, \ldots, v_L（ L \geq 1 ）であって、以下の条件をすべて満たすものを指します。

  • v_0 = 1 かつ v_L = N である。
  • 各 j （ 1 \leq j \leq L ）について、中継局 v_{j-1} と中継局 v_j を結ぶトンネルが存在する。
  • v_0, v_1, \ldots, v_L はすべて異なる（同じ中継局を2度以上通らない）。

この経路は L 本のトンネルを通過します。この L を、その経路が通過するトンネルの本数と呼びます。

コスト削減のため、高橋君は通過するトンネルの本数をできるだけ少なくしたいと考えています。

経路上のすべてのトンネルの幅が K センチメートル以上である経路が存在するかどうかを判定し、存在する場合はそのような経路の中で通過するトンネルの本数の最小値を出力してください。存在しない場合は -1 を出力してください。

制約

  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq 2 \times 10^5
  • 1 \leq K \leq 10^9
  • 1 \leq U_i < V_i \leq N (1 \leq i \leq M)
  • 1 \leq W_i \leq 10^9 (1 \leq i \leq M)
  • 同じ中継局の組を結ぶトンネルは高々1本である
  • 入力はすべて整数である

入力

N M K
U_1 V_1 W_1
U_2 V_2 W_2
\vdots
U_M V_M W_M

1 行目には、中継局の数 N 、トンネルの数 M 、ケーブル束の幅 K （センチメートル）が、スペース区切りで与えられる。

続く M 行のうち i 行目 (1 \leq i \leq M) には、 i 番目のトンネルが結ぶ2つの中継局の番号 U_i , V_i と、そのトンネルの幅 W_i （センチメートル）が、スペース区切りで与えられる。

出力

中継局 1 から中継局 N まで、経路上のすべてのトンネルの幅が K センチメートル以上である経路が存在する場合は、そのような経路の中で通過するトンネルの本数の最小値を 1 行で出力してください。

そのような経路が存在しない場合は、 -1 を出力してください。

入力例 1

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

出力例 1

3

入力例 2

4 4 10
1 2 15
1 3 5
2 3 8
3 4 12

出力例 2

-1

入力例 3

8 10 4
1 2 3
1 3 10
1 4 7
2 5 6
3 5 5
4 6 8
5 7 2
5 8 9
6 7 12
7 8 6

出力例 3

3

Score : 366 pts

Problem Statement

Takahashi is working as a network engineer at a telecommunications company and is in charge of planning the installation of fiber optic cables.

There are N relay stations in the city, numbered from 1 to N. There are also M underground tunnels, each connecting two different relay stations bidirectionally. The i-th tunnel (1 \leq i \leq M) connects relay station U_i and relay station V_i, and has a width of W_i centimeters.

Takahashi wants to install a fiber optic cable bundle of width K centimeters from the data center at relay station 1 to the customer building at relay station N. In order to pass the cable bundle through a tunnel, the width of that tunnel must be at least K centimeters. Therefore, all tunnels along the installation route must have a width of at least K centimeters.

Here, a path from relay station 1 to relay station N is a sequence of relay stations v_0, v_1, \ldots, v_L (L \geq 1) satisfying all of the following conditions:

  • v_0 = 1 and v_L = N.
  • For each j (1 \leq j \leq L), there exists a tunnel connecting relay station v_{j-1} and relay station v_j.
  • v_0, v_1, \ldots, v_L are all distinct (no relay station is visited more than once).

This path passes through L tunnels. We call this L the number of tunnels traversed by the path.

To reduce costs, Takahashi wants to minimize the number of tunnels traversed.

Determine whether there exists a path where all tunnels along the path have a width of at least K centimeters. If such a path exists, output the minimum number of tunnels traversed among all such paths. If no such path exists, output -1.

Constraints

  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq 2 \times 10^5
  • 1 \leq K \leq 10^9
  • 1 \leq U_i < V_i \leq N (1 \leq i \leq M)
  • 1 \leq W_i \leq 10^9 (1 \leq i \leq M)
  • There is at most one tunnel connecting any pair of relay stations
  • All input values are integers

Input

N M K
U_1 V_1 W_1
U_2 V_2 W_2
\vdots
U_M V_M W_M

The first line contains the number of relay stations N, the number of tunnels M, and the width of the cable bundle K (in centimeters), separated by spaces.

The i-th of the following M lines (1 \leq i \leq M) contains the numbers of the two relay stations U_i, V_i connected by the i-th tunnel, and the width W_i (in centimeters) of that tunnel, separated by spaces.

Output

If there exists a path from relay station 1 to relay station N where all tunnels along the path have a width of at least K centimeters, output the minimum number of tunnels traversed among all such paths on a single line.

If no such path exists, output -1.

Sample Input 1

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

Sample Output 1

3

Sample Input 2

4 4 10
1 2 15
1 3 5
2 3 8
3 4 12

Sample Output 2

-1

Sample Input 3

8 10 4
1 2 3
1 3 10
1 4 7
2 5 6
3 5 5
4 6 8
5 7 2
5 8 9
6 7 12
7 8 6

Sample Output 3

3