给定一个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