1074. Minimum Weighted Sum to All Reachable Nodes

Given a directed weighted graph with n nodes and edges [u, v, w] (w >= 0) and a source src, return the sum of the shortest-path distances from src to every node reachable from src (including src itself, whose distance is 0). The input is JSON {n, edges, src}.

Input: JSON {n, edges, src} with edges [u, v, w].

Output: Integer — the sum of reachable shortest distances.

Examples

Input: {"n":4,"edges":[[0,1,2],[0,2,5],[1,2,1],[2,3,3]],"src":0}
Output: 11
Explanation: 0+2+3+6=11.

Input: {"n":1,"edges":[],"src":0}
Output: 0
Explanation: Only the source.

Input: {"n":3,"edges":[[0,1,4]],"src":0}
Output: 4
Explanation: Node 2 unreachable, so only 0+4.

Constraints

• 1<=n<=10^5
• w>=0
• directed

Asked by