Johnson shortest paths

Given a directed weighted graph with n nodes (0..n-1) and edges [u, v, w] where w may be negative, compute the shortest-path distances from a given source to every node using Johnson's reweighting technique (a virtual node with 0-weight edges to all, one Bellman-Ford pass to get potentials, then Dijkstra on the reweighted non-negative graph, then undo the reweighting). Return a list dist where dist[v] is the shortest distance from src to v, or -1 if v is unreachable; if the graph contains a negative cycle, return an empty list. Assume 1 <= n <= 300.