Problem Description

Given a directed graph with $n$ nodes and $m$ weighted edges, find the shortest path lengths between all pairs of nodes. The length of a path is defined as the sum of the weights of all edges on the path.

Notes:

1. Edge weights may be negative, and the graph may contain multiple edges and self-loops.
2. Some test cases are designed to challenge the $n$-round SPFA algorithm.

Input Format

The first line contains two integers $n$ and $m$, representing the number of nodes and edges in the directed graph, respectively.

The following $m$ lines each contain three integers $u$, $v$, and $w$, indicating a directed edge from node $u$ to node $v$ with a weight of $w$.

Output Format

If a negative cycle exists in the graph, output a single line containing $-1$.

If no negative cycle exists:

Output $n$ lines: Let $dis_{i,j}$ be the shortest path from node $i$ to node $j$. On the $i$-th line, output $\sum_{j=1}^n j \times dis_{i,j}$, noting that this result may exceed the int storage range.

If there is no path from $i$ to $j$, then $dis_{i,j}=10^9$; if $i=j$, then $dis_{i,j}=0$.

Sample Input and Output

Sample Input #1

5 7
1 2 4
1 4 10
2 3 7
4 5 3
4 2 -2
3 4 -3
5 3 4

Sample Output #1

128
1000000072
999999978
1000000026
1000000014

Sample Input #2

5 5
1 2 4
3 4 9
3 4 -3
4 5 3
5 3 -2

Sample Output #2

-1

Notes

Sample Explanation

The left graph is from Sample #1, and the shortest path answer matrix is:

0 4 11 8 11 
1000000000 0 7 4 7 
1000000000 -5 0 -3 0 
1000000000 -2 5 0 3 
1000000000 -1 4 1 0 

The right graph is from Sample #2, where the red edges form a negative cycle. Note that the given graph may not be connected.

Data Range

For $100\%$ of the data, $1 \leq n \leq 3 \times 10^3$, $1 \leq m \leq 6 \times 10^3$, $1 \leq u, v \leq n$, $-3 \times 10^5 \leq w \leq 3 \times 10^5$.

For $20\%$ of the data, $1 \leq n \leq 100$, and no negative cycles exist (useful for verifying the correctness of the Floyd algorithm).

For another $20\%$ of the data, $w \geq 0$ (useful for verifying the correctness of the Dijkstra algorithm).

Updated: Added a hack data set specifically targeting the SLF optimization of the SPFA algorithm.

见题面 Input 部分

见题面 Output 部分