当前没有测试数据。

题目描述

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

输入格式

第一行一个整数 $T$，表示有 $T$ 组数据。

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

接下来 $m$ 行，每行三个整数 $x, y, z$，代表从 $x$ 到 $y$ 有长度为 $z$ 的边，点的编号从 $1$ 到 $n$。$T \le 10, n \le 10000, m \le 20000, |z| \le 10000$，所有数据的 $n$ 之和 $\le 30000$，所有数据的 $m$ 之和 $\le 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