#4255. 「2022.12八级」 最短路 暂未评定

时间限制:1000 ms 内存限制:128 MiB 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: root

题目描述

给定一个n个点, m条边的有向图, 求从点S出发, 到其它所有点的最短路径。

输入格式

第一行一个整数T, 表示有T组数据 对于每组测试数据, 第一行三个整数n, m, S, 表示有n个点, m条边, 起点为S。

接下来m行, 每行三个整数x, y, z, 代表从x到y有长度为z的边 点的编号从1到n T <= 10, n <= 10000, m <= 20000, |z| <= 10000。

所有数据的n之和 <= 30000, 所有数据的m之和 <= 60000.

输出格式

对于每组数据: 如果从S点出发可以走入负圈 (即到某些点的最短路径可以无限小), 那么输出一行Error。

否则, 输出一行用空格分隔的n个整数, 其中第i个整数表示从S点到i点的最短路长度。

如果从S点无法到达i点, 则第i个输出为”null”.

样例

样例输入

4
5 7 1
1 2 3
2 3 4
3 4 8
1 3 9
4 5 1
1 4 5
1 5 10
4 4 1
1 2 -4
2 3 8
1 3 5
3 4 0
3 3 2
1 2 -3
2 3 -4
3 1 6
4 2 1
1 2 1
3 4 2

样例输出

0 3 7 5 6
0 -4 4 4
Error
0 1 null null