D - 最安通勤ルート 解説 /

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

配点 : 400 点

問題文

高橋君は N 個の駅が M 本の路線で結ばれた鉄道ネットワークを利用して通勤しています。駅には 1 から N までの番号が付けられており、路線 i は駅 U_i と駅 V_i を双方向に結び、運賃が C_i 円かかります。

高橋君は駅 1 にある自宅の最寄り駅から、駅 N にある職場の最寄り駅まで毎日通勤する必要があります。高橋君が使える交通費の予算は K 円しかないため、運賃の合計が K 円以下となるルートを見つけなければなりません。

ここで、ルートとは、駅 1 から出発し路線を順に辿って駅 N へ到達する道順のことを指します。同じ駅を複数回訪れたり、同じ路線を複数回利用したりすることも許されます。ルートの運賃の合計とは、そのルートで利用した路線の運賃をすべて足し合わせたものです。ある路線を複数回利用した場合は、その回数分だけ運賃がかかります。

駅 1 から駅 N へ運賃の合計が K 円以下で到達できるルートが存在するならば、そのようなルートにおける運賃の合計の最小値を出力してください。そのようなルートが存在しない場合は -1 を出力してください。

制約

  • 2 \leq N \leq 10^5
  • 1 \leq M \leq 2 \times 10^5
  • 1 \leq K \leq 10^9
  • 1 \leq U_i, V_i \leq N
  • U_i \neq V_i
  • 同じ 2 駅間を結ぶ路線が複数存在することもある
  • 1 \leq C_i \leq 10^9
  • 入力はすべて整数である

入力

N M K
U_1 V_1 C_1
U_2 V_2 C_2
\vdots
U_M V_M C_M
  • 1 行目には、駅の数を表す N 、路線の数を表す M 、高橋君の交通費の予算を表す K が、スペース区切りで与えられる。
  • 2 行目から M + 1 行目では、路線の情報が M 行で与えられる。
  • 1 + i 行目では、路線 i が結ぶ 2 つの駅 U_i , V_i と運賃 C_i がスペース区切りで与えられる。

出力

駅 1 から駅 N へ運賃の合計が K 円以下で到達できるルートが存在する場合、その運賃の合計の最小値を 1 行で出力せよ。存在しない場合は -1 を 1 行で出力せよ。

入力例 1

4 4 10
1 2 3
2 4 5
1 3 7
3 4 2

出力例 1

8

入力例 2

3 2 5
1 2 3
2 3 4

出力例 2

-1

入力例 3

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

出力例 3

8

Score : 400 pts

Problem Statement

Takahashi commutes using a railway network consisting of N stations connected by M lines. The stations are numbered from 1 to N. Line i bidirectionally connects station U_i and station V_i, with a fare of C_i yen.

Takahashi needs to commute every day from station 1, the nearest station to his home, to station N, the nearest station to his workplace. Since Takahashi's transportation budget is only K yen, he must find a route whose total fare is at most K yen.

Here, a route refers to a path starting from station 1 and following lines in sequence to reach station N. It is permitted to visit the same station multiple times or use the same line multiple times. The total fare of a route is the sum of the fares of all lines used in that route. If a line is used multiple times, the fare is charged for each use.

If there exists a route from station 1 to station N with a total fare of at most K yen, output the minimum total fare among all such routes. If no such route exists, output -1.

Constraints

  • 2 \leq N \leq 10^5
  • 1 \leq M \leq 2 \times 10^5
  • 1 \leq K \leq 10^9
  • 1 \leq U_i, V_i \leq N
  • U_i \neq V_i
  • There may be multiple lines connecting the same pair of stations
  • 1 \leq C_i \leq 10^9
  • All input values are integers

Input

N M K
U_1 V_1 C_1
U_2 V_2 C_2
\vdots
U_M V_M C_M
  • The first line contains N representing the number of stations, M representing the number of lines, and K representing Takahashi's transportation budget, separated by spaces.
  • From the 2nd line to the (M + 1)-th line, information about the M lines is given.
  • The (1 + i)-th line contains the two stations U_i, V_i connected by line i and the fare C_i, separated by spaces.

Output

If there exists a route from station 1 to station N with a total fare of at most K yen, output the minimum total fare in one line. If no such route exists, output -1 in one line.

Sample Input 1

4 4 10
1 2 3
2 4 5
1 3 7
3 4 2

Sample Output 1

8

Sample Input 2

3 2 5
1 2 3
2 3 4

Sample Output 2

-1

Sample Input 3

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

Sample Output 3

8