暂无测试数据。

Description

给定一个 \(n\) 个点，\(m\) 条有向边的带非负权图，请你计算从 \(s\) 出发，到每个点的距离。

数据保证你能从 \(s\) 出发到任意点。

Format

Input

第一行为三个正整数 \(n\), \(m\), \(s\)。

第二行起 \(m\) 行，每行三个非负整数 \(u_i\), \(v_i\), \(w_i\)，表示从 \(u_i\) 到 \(v_i\) 有一条权值为 \(w_i\) 的有向边。

Output

输出一行 \(n\) 个空格分隔的非负整数，表示 \(s\) 到每个点的距离。

Sample 1

Input

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

Output

0 2 4 3

Limitation

对于 \(100\%\) 的数据：

• \(1 \le n \le 10^5\);
• \(1 \le m \le 2\times10^5\);
• \(s=1\);
• \(1 \le u_i,v_i \le n\);
• \(0 \le w_i \le 10^9\);
• \(0 \le \sum w_i \le 10^9\);

1s, 126MB.

Source

update by Shuchong