A courier network is a weighted undirected graph of n stations (numbered 0 to n-1) connected by roads, each with a positive integer travel cost usable in both directions.
A delivery must start at station s, end at station t, and pass through a mandatory checkpoint station r at some point along the way (the order of stations otherwise being free, and stations may be revisited). Find the minimum possible total travel cost of such a trip, or report that it is impossible.
Because all costs are positive, the cheapest trip through r costs exactly the shortest-path distance from s to r plus the shortest-path distance from r to t.
Input format
Line 1: two integers n and m.
Each of the next m lines: three integers u v w, a two-way road between u and v with cost w.
Final line: three integers s r t (start, required checkpoint, target).
Output format
A single integer: the minimum total cost of a trip from s to t passing through r, or -1 if no such trip exists.
Constraints
- 1 <= n <= 100000
- 0 <= m <= 200000
- 0 <= s, r, t, u, v <= n-1
- 1 <= w <= 1000000