给定一个包含 n 个结点和 m 条带权边的有向图，求所有点对间的最短路径长度，一条路径的长度定义为这条路径上所有边的权值和。
第 1 行：2 个整数 n, m，表示给定有向图的结点数量和有向边数量。
接下来 m 行：每行 3 个整数 u, v, w，表示有一条权值为 w 的有向边从编号为 u 的结点连向编号为 v 的结点。
若图中存在负环，输出仅一行 -1。
若图中不存在负环：
输出 n 行：令 $dis{i,j} 为从 i 到 j 的最短路，在第 i 行输出 \sum\limits{j=1}^n j \times dis_{i,j}$，注意这个结果可能超过 int 存储范围。
如果不存在从 i 到 j 的路径，则 $dis{i,j} = 10^9；如果 i = j，则 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
5 7 1 2 4 1 4 10 2 3 7 4 5 3 4 2 -2 3 4 -3 5 3 4
5 5 1 2 4 3 4 9 3 4 -3 4 5 3 5 3 -2
-1
对于 100\% 的数据，1 \le n \le 3 \times 10^3，1 \le m \le 6 \times 10^3，1 \le u, v \le n，-3 \times 10^5 \le w \le 3 \times 10^5。