给定一个包含 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$。

对于 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。