A47209.【模板】全源最短路

给定一个包含 $n$ 个顶点和 $m$ 条有向边的带权图，请计算图中所有顶点对之间的最短路径距离。

图的性质

• 图中可能存在负权边
• 图中可能存在重边和自环
• 需要检测图中是否存在负权回路（负环）

输入数据共 $m+1$ 行：

• 第 1 行包含两个整数 $n$ 和 $m$，分别表示图的顶点数和边数。
• 接下来 $m$ 行，每行包含三个整数 $u$, $v$, $w$，表示存在一条从顶点 $u$ 指向顶点 $v$ 的有向边，边权为 $w$。

根据图中是否存在负环，输出不同内容：

1. 如果存在负环：

   • 仅输出一行 -1

2. 如果不存在负环：

   • 输出 $n$ 行，每行 $n$ 个整数
   • 第 $i$ 行第 $j$ 个数表示顶点 $i$ 到顶点 $j$ 的最短距离 $dis(i,j)$
   • 如果顶点 $i$ 无法到达顶点 $j$，则 $dis(i,j) = 10^9$
   • 特别地，$dis(i,i) = 0$（顶点到自身的距离为 0）

样例1说明：

• 输出的是一个 $5 \times 5$ 的最短距离矩阵
• 例如 $dis(1,3)=11$ 表示顶点1到顶点3的最短距离为11
• $dis(3,2)=-5$ 表示顶点3到顶点2的最短距离为-5（存在负权边）
• 所有无法到达的点对距离均为 $10^9$

样例2说明：

• 图中存在一个负权回路（3→4→5→3），该回路的权值和为-2，因此输出-1

数据范围

• 顶点数：$1 \leq n \leq 500$
• 边数：$1 \leq m \leq 1000$
• 边权范围：$-3 \times 10^5 \leq w \leq 3 \times 10^5$
• 特殊性质：20%的数据保证不存在负权边