Migrated from Lutece 2730 纯白色的少年郎，如今只身在何方

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

图图星球的晚晚国的公主阿晚一袭红衣坐在沙丘上，盼着与她少年时期定下十年之约的王子，可终究，没能等到他。既然等不到，那就去找他吧。图图星球上所有的国家都由非负权值的有向道路相互连接，该星球上没有远程通讯功能。阿晚记性很差，她不记得王子是哪个国家的了，但她手上有半块王子留下的玉佩。因此她决定派使臣们去每个国家问一问这是哪个王子留下的半块玉佩。现在她需要知道其他所有国家到晚晚国的最短距离，以便安排使臣们的行程。 如果晚晚国不能到达第 $i$ 个国家，则第 $i$ 行输出 $-1$。

Input

第一行为三个正整数 $n$，$m$，$s$，分别表示共有 $n$ 个国家，$m$ 条道路，晚晚国位于编号 $s$。 第二行起 $m$ 行，每行三个非负整数 $u_i$，$v_i$，$w_i$，表示从编号为 $u_i$ 的国家到编号为 $v_i$ 的国家有一条权值为 $w_i$ 的有向道路。

Output

输出 $n$ 行整数，每行有且只有一个数。第 $i$ 行表示晚晚国 $s$ 到编号为 $i$ 的国家的最短距离。

Samples

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

0 
2
1
3

Constraints

$1 \leq n \leq 10^5$；

$1 \leq m \leq 2\times 10^5$；

$1 \leq s \leq n$；

$1 \leq u_i, v_i\leq n$；

$0 \leq w_i \leq 10 ^ 9$,

Resources

2022 UESTC ICPC Training for Graph