CF1528D It's a bird! No, it's a plane! No, it's AaParsa!

Shaazzzland 有 $n$ 个城市，编号从 $0$ 到 $n-1$。Ghaazzzland 是 Shaazzzland 的死敌，由 AaParsa 统治。 作为 Ghaazzzland 情报机构的负责人，AaParsa 正在对 Shaazzzland 执行历史上最重要的间谍任务。 AaParsa 在 Shaazzzland 的城市中安置了 $m$ 门传送炮。第 $i$ 门炮安置在城市 $a_i$，最初指向城市 $b_i$。 保证每个城市至少有一门传送炮安置，并且同一城市的炮不会同时指向同一个城市（即所有 $(a_i, b_i)$ 都不同）。 这些炮采用了非常先进的技术，每秒都会旋转。也就是说，如果第 $i$ 门炮在某一秒指向城市 $x$，那么下一秒会指向城市 $(x+1) \bmod n$。 顾名思义，传送炮用于运输，特别是人员运输。如果你使用第 $i$ 门炮发射自己到它当前指向的城市，你将在空中飞行 $c_i$ 秒后到达目标城市。 具体来说，如果你在第 $s$ 秒使用第 $i$ 门炮（前提是你当前在城市 $a_i$），你会被发射到城市 $(b_i + s) \bmod n$，并在 $c_i$ 秒后（即第 $s + c_i$ 秒）到达那里。注意，发射后炮会继续旋转，但你在空中时不会改变方向。 AaParsa 想利用这些传送炮在 Shaazzzland 的城市间旅行，他可以从第 $0$ 秒开始出发。为了充分利用这些炮，他需要知道从城市 $v$ 到城市 $u$ 所需的最少时间，对于每一对城市 $(u, v)$ 都要计算。 注意，AaParsa 可以选择在任意城市停留任意长时间。

第一行包含两个整数 $n$ 和 $m$，表示城市数和传送炮数，满足 $2 \le n \le 600$，$n \le m \le n^2$。 接下来 $m$ 行，每行包含三个整数 $a_i$、$b_i$ 和 $c_i$，表示第 $i$ 门炮安置在城市 $a_i$，最初指向城市 $b_i$，使用该炮需要 $c_i$ 秒到达目标城市。$0 \le a_i, b_i \le n-1$，$1 \le c_i \le 10^9$。 保证每个城市至少有一门传送炮安置，并且同一城市的炮不会同时指向同一个城市（即所有 $(a_i, b_i)$ 都不同）。

输出 $n$ 行，每行包含 $n$ 个整数。 第 $i$ 行第 $j$ 个整数表示从城市 $i$ 到城市 $j$ 所需的最少时间。

在第一个样例中，从 $0$ 到 $2$ 的一种可能路径如下： 1. 在 $0$ 停留 $1$ 秒。 2. 使用第一门炮，$1$ 秒后到达 $2$。 注意：你也可以在第 $0$ 秒使用第二门炮，但那样到达 $2$ 需要 $3$ 秒。 由 ChatGPT 4.1 翻译