A network has n nodes connected by m two-way links. Each link u v w has a non-negative cost w to traverse. Given a source node and a target node, compute the minimum possible total cost of a route from source to target.
The minimum total cost is uniquely determined even though several routes may achieve it. If the target is unreachable from the source, print -1. If the source equals the target, the cost is 0.
Note: multiple links may connect the same pair of nodes, possibly with different costs; a route may only ever benefit from the cheaper one.
Input format
Line 1: two integers n and m.
Next m lines: three integers u v w (nodes 0-indexed) \u2014 a two-way link between u and v with cost w.
Last line: two integers s t \u2014 the source and the target node.
Output format
A single integer: the minimum total cost of a route from s to t, or -1 if t is unreachable.
Constraints
- 1 \u2264 n \u2264 100000
- 0 \u2264 m \u2264 200000
- 0 \u2264 u, v, s, t < n
- 0 \u2264 w \u2264 1000000
- Links may repeat between the same pair of nodes. There are no self-links (
u \u2260 v).