Background

洛谷P4779 ?

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

\(n=10^3\) , \(m=987654\)
\(1<=w_{i}<=10^9\)
150ms for each test case.
约为std1.5倍

Source

zyc Original