← 返回题目列表

Codeforces · 1528/D

D. 这是一只鸟!不,这是一架飞机!不,是阿帕莎!

中文机器翻译题面 查看原题

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$$$ 处。