D - Fastest Delivery Route Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

高橋君は配達員として働いています。今日は荷物を届けるために、できるだけ早くお届け先に向かわなければなりません。

配達エリアには N 個の地点があり、地点は 1 から N まで番号が付けられています。高橋君は地点 1 にある配送センターからスタートし、地点 N にあるお届け先を目指します。

地点間には M 本の一方通行の道路があります。i 番目の道路（1 \leq i \leq M）は地点 U_i から地点 V_i へ向かう一方通行で、この道路を通るのに C_i の時間がかかります。同じ地点の組 (U_i, V_i) に対して複数の道路が存在することもあります。

高橋君は同じ地点を複数回通ることもできます。配送センター（地点 1）からお届け先（地点 N）までの最短所要時間を求めてください。

なお、地点 1 から地点 N へ到達可能であることは保証されています。

制約

  • 2 \leq N \leq 10^5
  • 1 \leq M \leq 2 \times 10^5
  • 1 \leq U_i \leq N
  • 1 \leq V_i \leq N
  • U_i \neq V_i
  • 1 \leq C_i \leq 10^9
  • 同じ (U_i, V_i) の組が複数回与えられることがある
  • 地点 1 から地点 N へ到達可能である
  • 入力はすべて整数である

入力

N M
U_1 V_1 C_1
U_2 V_2 C_2
\vdots
U_M V_M C_M
  • 1 行目には、地点の数 N と道路の数 M がスペース区切りで与えられる。
  • 続く M 行のうち i 行目（1 \leq i \leq M）には、i 番目の道路の始点 U_i、終点 V_i、通過にかかる時間 C_i がスペース区切りで与えられる。この道路は地点 U_i から地点 V_i への一方通行である。

出力

地点 1 から地点 N へ到達するまでの最短所要時間を整数で 1 行に出力せよ。

入力例 1

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

出力例 1

6

入力例 2

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

出力例 2

26

入力例 3

10 15
1 2 1000000000
1 3 500000000
2 4 300000000
3 4 200000000
3 5 400000000
4 6 100000000
5 6 150000000
5 7 250000000
6 7 50000000
6 8 200000000
7 8 100000000
7 9 300000000
8 9 150000000
8 10 400000000
9 10 100000000

出力例 3

1200000000

Score : 400 pts

Problem Statement

Takahashi works as a delivery person. Today, he must head to the delivery destination as quickly as possible to deliver a package.

The delivery area contains N locations, numbered from 1 to N. Takahashi starts from the distribution center at location 1 and aims to reach the delivery destination at location N.

There are M one-way roads between the locations. The i-th road (1 \leq i \leq M) is a one-way road from location U_i to location V_i, and it takes C_i time to travel along this road. There may be multiple roads for the same pair of locations (U_i, V_i).

Takahashi may pass through the same location more than once. Find the shortest time required to travel from the distribution center (location 1) to the delivery destination (location N).

It is guaranteed that location N is reachable from location 1.

Constraints

  • 2 \leq N \leq 10^5
  • 1 \leq M \leq 2 \times 10^5
  • 1 \leq U_i \leq N
  • 1 \leq V_i \leq N
  • U_i \neq V_i
  • 1 \leq C_i \leq 10^9
  • The same pair (U_i, V_i) may be given multiple times
  • Location N is reachable from location 1
  • All input values are integers

Input

N M
U_1 V_1 C_1
U_2 V_2 C_2
\vdots
U_M V_M C_M
  • The first line contains the number of locations N and the number of roads M, separated by a space.
  • The following M lines each describe a road: the i-th of these lines (1 \leq i \leq M) contains the starting point U_i, the ending point V_i, and the travel time C_i of the i-th road, separated by spaces. This road is one-way from location U_i to location V_i.

Output

Print the shortest time required to travel from location 1 to location N as an integer on a single line.

Sample Input 1

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

Sample Output 1

6

Sample Input 2

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

Sample Output 2

26

Sample Input 3

10 15
1 2 1000000000
1 3 500000000
2 4 300000000
3 4 200000000
3 5 400000000
4 6 100000000
5 6 150000000
5 7 250000000
6 7 50000000
6 8 200000000
7 8 100000000
7 9 300000000
8 9 150000000
8 10 400000000
9 10 100000000

Sample Output 3

1200000000