Dijkstra's algorithm fails when edges can be negative (a refund, a downhill energy gain, an exchange-rate advantage). Write BellmanFord. Read n m source and m directed edges u v weight. Relax every edge, in input order, n − 1 times (stop early when a whole round changes nothing). Then run one more round: if any distance can still improve, a negative cycle is reachable.
Print the number of rounds used (not checked), then either Negative cycle reachable from s: shortest paths are not defined or, for each vertex, the distance and the path (unreachable if there is none).
For the input
5 10 0
0 1 6
0 2 7
1 2 8
1 3 5
1 4 -4
2 3 -3
2 4 9
3 1 -2
4 0 2
4 3 7
the program prints
Rounds used: 3
0 -> 0: 0 path 0
0 -> 1: 2 path 0 2 3 1
0 -> 2: 7 path 0 2
0 -> 3: 4 path 0 2 3
0 -> 4: -2 path 0 2 3 1 4