D - 最短配達ルート 解説 /

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

配点 : 400 点

問題文

高橋君は、ある都市で配達員として働いています。この都市には N 個の地点があり、各地点には 1 から N までの番号が付けられています。

都市には M 本の道路があり、各道路は2つの地点を双方向に結んでいます。i 番目の道路 (1 \leq i \leq M) は地点 A_i と地点 B_i を結んでおり、この道路を通るのに C_i 分かかります。同じ2地点間を結ぶ道路が複数存在することもあります。

高橋君は、配達センターがある地点 1 から出発し、道路を通って届け先である地点 N まで荷物を届けます。地点 1 から地点 N へ至る経路とは、地点の列 v_0 = 1, v_1, v_2, \ldots, v_k = N (k \geq 1) であって、各 j (0 \leq j \leq k-1) について地点 v_{j} と地点 v_{j+1} を結ぶ道路が少なくとも1本存在するようなものを指します。同じ地点を複数回通ってもかまいません。

経路の所要時間は次のように定まります。各 j (0 \leq j \leq k-1) について、地点 v_j と地点 v_{j+1} を結ぶ道路の中から通る道路を1本選び、選んだ道路の所要時間の合計を経路の所要時間とします。

地点 1 から地点 N へ至る経路が存在する場合は、経路の所要時間（分）の最小値を出力してください。経路が存在しない場合は -1 を出力してください。

制約

  • 2 \leq N \leq 10^5
  • 0 \leq M \leq 2 \times 10^5
  • 1 \leq A_i \leq N
  • 1 \leq B_i \leq N
  • A_i \neq B_i（自己ループはない）
  • 1 \leq C_i \leq 10^9
  • 入力はすべて整数

入力

N M
A_1 B_1 C_1
A_2 B_2 C_2
\vdots
A_M B_M C_M
  • 1 行目には、地点の個数 N と道路の本数 M が、スペース区切りで与えられる。
  • 続く M 行の i 番目 (1 \leq i \leq M) には、i 番目の道路が結ぶ2つの地点の番号 A_i, B_i と、その道路の所要時間（分） C_i が、スペース区切りで与えられる。

出力

地点 1 から地点 N へ至る経路の所要時間の最小値を1行に出力してください。経路が存在しない場合は -1 を出力してください。

入力例 1

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

出力例 1

8

入力例 2

3 1
1 2 10

出力例 2

-1

入力例 3

6 9
1 2 7
1 3 9
1 5 14
2 3 10
2 4 15
3 4 11
3 5 2
4 6 6
5 6 9

出力例 3

20

Score : 400 pts

Problem Statement

Takahashi works as a delivery person in a city. The city has N locations, each numbered from 1 to N.

The city has M roads, each connecting two locations bidirectionally. The i-th road (1 \leq i \leq M) connects location A_i and location B_i, and it takes C_i minutes to travel along this road. There may be multiple roads connecting the same pair of locations.

Takahashi starts from location 1, where the delivery center is, and delivers a package to location N by traveling along roads. A path from location 1 to location N is a sequence of locations v_0 = 1, v_1, v_2, \ldots, v_k = N (k \geq 1) such that for each j (0 \leq j \leq k-1), there exists at least one road connecting location v_{j} and location v_{j+1}. The same location may be visited multiple times.

The travel time of a path is determined as follows. For each j (0 \leq j \leq k-1), one road is chosen from among the roads connecting location v_j and location v_{j+1}, and the total of the travel times of the chosen roads is the travel time of the path.

If a path from location 1 to location N exists, output the minimum travel time (in minutes). If no path exists, output -1.

Constraints

  • 2 \leq N \leq 10^5
  • 0 \leq M \leq 2 \times 10^5
  • 1 \leq A_i \leq N
  • 1 \leq B_i \leq N
  • A_i \neq B_i (no self-loops)
  • 1 \leq C_i \leq 10^9
  • All inputs are integers

Input

N M
A_1 B_1 C_1
A_2 B_2 C_2
\vdots
A_M B_M C_M
  • The first line contains the number of locations N and the number of roads M, separated by a space.
  • The i-th (1 \leq i \leq M) of the following M lines contains the numbers of the two locations A_i, B_i connected by the i-th road and the travel time (in minutes) C_i of that road, separated by spaces.

Output

Output the minimum travel time of a path from location 1 to location N on a single line. If no path exists, output -1.

Sample Input 1

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

Sample Output 1

8

Sample Input 2

3 1
1 2 10

Sample Output 2

-1

Sample Input 3

6 9
1 2 7
1 3 9
1 5 14
2 3 10
2 4 15
3 4 11
3 5 2
4 6 6
5 6 9

Sample Output 3

20