Problem Description

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

Note:

1. Edge weights may be negative, and the graph may contain multiple edges and self-loops.
2. Some testdata is designed to make running SPFA for $n$ rounds fail.

Input Format

Line $1$: Two integers $n, m$, representing the number of nodes and the number of directed edges in the given graph.

Next $m$ lines: Each line contains three integers $u, v, w$, meaning there is a directed edge of weight $w$ from node $u$ to node $v$.

Output Format

If the graph contains a negative cycle, output only one line: $-1$.

If the graph does not contain a negative cycle:

Output $n$ lines. Let $dis_{i,j}$ be the shortest path from $i$ to $j$. On line $i$, output $\sum\limits_{j=1}^n j\times dis_{i,j}$. Note that this value may exceed the range of int.

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

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

128
1000000072
999999978
1000000026
1000000014

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

-1

Hint

[Sample Explanation]

The left figure shows the directed graph given in sample $1$. The answer matrix formed by the shortest paths 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 figure shows the directed graph given in sample $2$. The edges marked in red form a negative cycle. Note that the given graph may be disconnected.

[Constraints]

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 there is no negative cycle (can be used to verify Floyd correctness).

For another $20\%$ of the data, $w\ge 0$ (can be used to verify Dijkstra correctness).

upd. Added a set of hack testdata: targeting the SLF optimization of SPFA.

Translated by ChatGPT 5