Description

Given a directed graph with $n$ nodes and $m$ directed edges with non-negative weights, please compute the distance from $s$ to every node.

The testdata guarantees that you can reach every node starting from $s$.

Input Format

The first line contains three positive integers $n, m, s$. Starting from the second line, there are $m$ lines. Each line contains three non-negative integers $u_i, v_i, w_i$, meaning there is a directed edge from $u_i$ to $v_i$ with weight $w_i$.

Output Format

Output one line with $n$ space-separated non-negative integers, representing the distance from $s$ to each node.

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

Hint

For the sample explanation, please refer to Template Problem with Random Data.

Constraints:

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

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

$s = 1$;

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

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

$0 \leq \sum w_i \leq 10 ^ 9$。

The testdata of this problem may continue to be updated, but it will not be rejudged. Please be informed.

2018.09.04 Data update from @zzq.

Translated by ChatGPT 5