No submission language available for this problem.

Background

Special for beginners, ^_^

Description

给出一个有向图，请输出从某一点出发到所有点的最短路径长度。

Format

Input

第一行包含三个整数 n, m, s，分别表示点的个数、有向边的个数、出发点的编号。

接下来 m 行每行包含三个整数 u, v, w，表示一条 u−>v 的，长度为 w 的边。

注意数据存在重边，例如：

• 1 2 2 表示 1->2 有权值为 2 的一条边
• 1 2 3 表示 1->2 还有一条权值为 3 的一条边

Output

输出一行 n 个整数，第 i 个表示 s 到第 i 个点的最短路径权值和，若无法到达则为 −1。

Samples

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

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

0 2 4 -1

Limitation

$1<=n,m<=1000$

$1<=u,v<=n$

$1<=w<=1000$

1s, 1024KiB for each test case.