该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

随着时代的发展，世界上出现了越来越多的人机，它们的出现，影响了很多人的生活。雪豹是一个人机猎杀者，每天的任务是猎杀各地区的人机。

人机 $u$ 和人机 $v$ 之间可能会存在一条单向路径，雪豹可以花费时间 $w$ 通过路径从 $u$ 走向 $v$（若 $u$ 和 $v$ 不存在路径，则无法通过）。

为了更好的猎杀人机，雪豹想知道，如果他从 人机 $s$ 处开始猎杀，那么他猎杀各个人机的最短耗时是多少（猎杀动作不耗时），如果某个人机无法猎杀，则猎杀这个人机的最短耗时为 inf。

输入格式

第一行给出一个正整数 $T \: (1 \leq T \leq 10)$，表示存在 $T$ 组测试数据。

对于每组测试数据，第一行给出三个正整数 $V, E, s \: (1 \leq s \leq V \leq 10^5, 1 \leq E \leq 2 \times 10^5)$，分别表示有多少个人机，多少条路径，猎杀的起点。

接下来 $E$ 行，每行给出三个正整数 $u, v, w \: (1 \leq u, v \leq V, 0 \leq w \leq 2^{32})$，表示人机 $u$ 和人机 $v$ 之间存在一条时间损耗为 $w$ 的路径。

输出格式

输出包括一行，$V$个整数，中间用空格分隔，输出不能包括末尾空格，表示雪豹猎杀各个人机的最短耗时。

输入输出样例

1
4 6 1
1 2 2
2 3 2
2 4 1
1 3 5
3 4 3
1 4 4

0 2 4 3

提示

十年OI一场空，不开long long见祖宗