Standard Bar Graphs · Shortest Path Problems O(N + M) · O(N + M)
A build pipeline's stages run one-way with per-stage tolls, and DevOps wants the cheapest toll total from stage 0 to every stage. Because no stage ever loops back, one pass in dependency order suffices: settle a stage's cheapest toll first, then relax its outgoing one-way edges — each edge relaxes once, forever.
Input: An integer N (vertices 0..N-1), the edge count M, and an edge list edges where [u, v, w] is a one-way edge u -> v with cost w.
Output: Return an array where entry i is the minimum cost from vertex 0 to i, or -1 if unreachable.
1 <= N <= 10^50 <= M <= 2 * 10^50 <= w <= 10^5Input: {"N":4,"M":4,"edges":[[0,1,2],[0,2,1],[1,3,3],[2,3,1]]}
Output: [0,2,1,2]
Stage 3 is cheapest via 0->2 (1) then 2->3 (1): total 2.
Input: {"N":3,"M":1,"edges":[[0,1,5]]}
Output: [0,5,-1]
Vertex 2 has no incoming edges, so it stays unreachable.