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.
Input format
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.
Output format
A single integer: the minimum total toll to get from junction 0 to junction n-1, or -1 if it cannot be reached.
Constraints
- 1 <= n <= 100000
- 0 <= m <= 200000
- 0 <= u, v <= n-1, u may differ from v
- 1 <= w <= 1000000
- There may be multiple roads between the same pair of junctions.