All-Pairs Shortest Paths in Directed Graphs

You are given a directed graph with \(n\) nodes and \(m\) weighted edges. The weight of a path is defined as the sum of the weights of its edges. Your task is to compute the shortest path length between every pair of nodes.

Note:

• Edge weights may be negative.
• The graph may contain multiple edges between the same pair of nodes and self-loops.
• Some test cases are designed such that using an \(O(n)\) SPFA (Shortest Path Faster Algorithm) for each node will not pass.

You can assume that there are no negative cycles in the graph.

Input Format:

The first line contains two integers \(n\) and \(m\) --- the number of nodes and edges respectively.

Then \(m\) lines follow, each containing three integers \(u\), \(v\) and \(w\) representing a directed edge from node \(u\) to node \(v\) with weight \(w\). The nodes are numbered from 1 to \(n\).

Output Format:

Print \(n\) lines. The \(i^{th}\) line should contain \(n\) space-separated tokens, where the \(j^{th}\) token is the shortest path distance from node \(i\) to node \(j\). If there is no path from node \(i\) to node \(j\), output INF for that entry. The distance from a node to itself is 0.

inputFormat

The first line of input contains two integers \(n\) and \(m\). Each of the next \(m\) lines contains three integers \(u\), \(v\), and \(w\) describing a directed edge from \(u\) to \(v\) with weight \(w\>.

outputFormat

Output \(n\) lines, each containing \(n\) space-separated values. The \(j^{th}\) value on the \(i^{th}\) line should be the shortest distance from node \(i\) to node \(j\), or INF if no path exists.

sample

4 4
1 2 3
2 3 4
3 4 5
1 4 15

0 3 7 12
INF 0 4 9
INF INF 0 5
INF INF INF 0