Service Mesh Shortest Path
A service mesh has services as nodes and weighted directed edges representing measured p99 hop latencies (ms). A canary controller routes new traffic along the lowest-cumulative-latency path between a source and target service. Find that path's total latency.
Problem
Given an integer n (number of services 0..n−1), a list of edges (u, v, w) with positive weight, a source s, and a target t, return the minimum total weight of any path from s to t. If no path exists, return −1.
Input
Integer n (1 ≤ n ≤ 10^4), list of m edges (0 ≤ m ≤ 5·10^4), each (u, v, w) with 1 ≤ w ≤ 10^4, plus integers s and t.
Output
A single integer — the minimum total weight, or −1 if unreachable.
Constraints
- 1 ≤ n ≤ 10,000
- 0 ≤ m ≤ 50,000
- All edge weights are positive — Dijkstra applies
- Multiple parallel edges allowed — pick the smallest weight
Examples
Example 1
Input
n = 4, edges = [(0,1,1), (1,2,2), (0,2,5), (2,3,1)], s = 0, t = 3
Output
4
Path 0→1→2→3 has weight 1+2+1=4. Path 0→2→3 has weight 5+1=6. Best is 4.
Example 2
Input
n = 2, edges = [], s = 0, t = 1
Output
-1
No path.