A container port connects n junctions (numbered 0 to n-1) by two-way haul roads. Each road joins two junctions and charges a positive integer toll every time it is used, in either direction.
A crane operator must move from junction 0 to junction n-1. Find the minimum possible total toll of a route, where the total toll of a route is the sum of the tolls of the roads it uses. If no route exists, report that it is impossible.
Line 1: two integers n and m (the number of junctions and the number of roads).
Each of the next m lines: three integers u v w, a two-way road between junctions u and v with toll w.
A single integer: the minimum total toll to get from junction 0 to junction n-1, or -1 if it cannot be reached.
Example 1
Input
4 4 0 1 3 1 3 4 0 2 5 2 3 2
Expected
7
Explanation
Route 0->1->3 costs 3+4=7 and route 0->2->3 costs 5+2=7; both are minimal, so the answer is 7.
Example 2
Input
3 1 0 1 2
Expected
-1
Explanation
Only junctions 0 and 1 are connected; junction 2 (which is n-1) cannot be reached, so the answer is -1.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →