Problem statement
You are given a directed weighted graph with N vertices and M edges. Find the cost of the second shortest route from S to T. A route may visit the same vertex or edge multiple times. Different routes are counted separately, even if their total costs are equal. Therefore, the second shortest route may have the same cost as the shortest route. If fewer than two routes exist, print -1. Self-loops and repeated edges are allowed. Routes are distinguished by their sequences of input edges; parallel input edges count as different choices. If S equals T, the empty route of cost 0 counts as the first route. Positive-cost routes returning to S may then supply the second route.
Input format
First line: N M. Next M lines: U V W. Last line: S T.
Output format
Print the cost of the second shortest route or -1.
Constraints
- 1 ≤ N ≤ 100000
- 0 ≤ M ≤ 200000
- 1 ≤ U, V, S, T ≤ N
- 1 ≤ W ≤ 10^9
- Use 64-bit integers for route costs.
Sample input
4 5 1 2 2 1 3 2 2 4 3 3 4 3 1 4 8 1 4
Sample output
5
Sample explanation
The distinct edge sequences 1 → 2 → 4 and 1 → 3 → 4 both cost 5. They occupy the first two places, so the second route costs 5.
Need a hint?
Modified Dijkstra that tracks the two smallest route costs per vertex, including equal costs. Repeated visits are allowed. Expected complexity: O((N + M) log N) for tracking two route entries per vertex.