Cheapest Route

Difficulty: 1700 4000 ms 128 MB

graphs shortest-paths

Roads have positive costs. Print the cheapest travel cost from city 1 to city N, or −1 if N is unreachable.

Input: the first line has N and M; each of the next M lines has u v w — an undirected road of cost w.

Output: the minimum cost 1 → N, or −1.

Constraints:

• 2 ≤ N ≤ 10⁴
• 1 ≤ M ≤ 2×10⁴
• 1 ≤ w ≤ 10⁶

Sample Tests

4 4
1 2 5
2 4 4
1 3 2
3 4 9

9

2 1
1 2 7

7

Read the Editorial