Shaazzzland 有 $$$n$$$ 个城市,编号从 $$$0$$$ 到 $$$n-1$$$。加兹领是沙兹领不朽的敌人,由阿帕萨统治。
作为加兹地情报机构的负责人,阿帕萨正在沙兹地执行加兹地历史上最重要的间谍任务。
AaParsa 在 Shaazzzland 的城市中安置了 $$$m$$$ 运输大炮。第 $$$i$$$ 大炮安装在城市 $$$a_i$$$ 中,最初指向城市 $$$b_i$$$。
保证每个 $$$n$$$ 城市内至少安置一门运输大炮,并且来自同一城市的两门大炮最初不会指向同一城市(也就是说,所有对 $$$(a_i, b_i)$$$ 都是不同的)。
AaParsa 使用非常先进的技术来建造大炮,大炮每秒旋转。换句话说,如果第$$$i$$$大炮在某一秒指向城市$$$x$$$,它将在下一秒瞄准城市$$$(x + 1) \mod n$$$。
顾名思义,运输炮是用于运输的,特别是用于人类运输的。如果您使用第 $$$i$$$ 号大炮向其当前指向的城市发射,您将在空中飞行 $$$c_i$$$ 秒,然后到达目标目的地。
如果你还是不明白,在第$$$s$$$秒使用第$$$i$$$大炮(只有当你当前在城市$$$a_i$$$时才可以使用)会将你射向城市$$$(b_i + s) \mod n$$$,你将在$$$c_i$$$秒后降落在那里(所以你会在第 $$$(s + c_i)$$$-th 秒)。另请注意,您最初发射的大炮每秒都会旋转,但在空中时您显然不会改变方向。
AaParsa想要在他的宏伟计划中使用大炮在Shaazzzland的城市之间旅行,并且他可以在第二个$$$0$$$开始旅行。为了充分利用它们,他需要知道使用每对城市 $$$(u, v)$$$ 的大炮从城市 $$$v$$$ 到达城市 $$$u$$$ 所需的最少秒数。
请注意,AaParsa 可以在城市中停留任意长时间。
输入
第一行包含两个整数 $$$n$$$ 和 $$$m$$$ $$$(2 \le n \le 600 , n \le m \le n^2)$$$ — 相应的城市和大炮的数量。
以下$$$m$$$行中的第$$$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$$$,经过它需要 $$$c_i$$$ 秒。
保证每个 $$$n$$$ 城市内至少安置一门运输大炮,并且来自同一城市的两门大炮最初不会指向同一城市(也就是说,所有对 $$$(a_i, b_i)$$$ 都是不同的)。
输出
打印 $$$n$$$ 行,每行应包含 $$$n$$$ 整数。
第 $$$i$$$ 行中的第 $$$j$$$ 个整数应等于从城市 $$$i$$$ 到达城市 $$$j$$$ 所需的最短时间。
示例
输入 #1
3 4 0 1 1 0 2 3 1 0 1 2 0 1
输出 #1
0 1 2 1 0 2 1 2 0
输入 #2
6 6 0 0 1 1 1 1 2 2 1 3 3 1 4 4 1 5 5 1
输出 #2
0 2 3 3 4 4 4 0 2 3 3 4 4 4 0 2 3 3 3 4 4 0 2 3 3 3 4 4 0 2 2 3 3 4 4 0
输入 #3
4 5 0 1 1 1 3 2 2 2 10 3 0 1 0 0 2
输出 #3
0 1 2 3 3 0 3 2 12 13 0 11 1 2 2 0
注意
在第一个示例中,从 $$$0$$$ 到 $$$2$$$ 的可能路径是:
1. 待在 $$$0$$$ 内,并在 $$$1$$$ 时间内不做任何事情。
2. 使用第一门大炮并在 $$$1$$$ 第二门后降落在 $$$2$$$ 处。