P4779 [Template] Single-Source Shortest Path (Standard Version).

On July 19, 2018, a student used a well-known algorithm very skillfully to find shortest paths in the problem [NOI Day 1 T1 Return Trip](https://www.luogu.org/problemnew/show/P4768). Then what? $100 \rightarrow 60$; $\text{Ag} \rightarrow \text{Cu}$; In the end, because of this, he failed to make a contract with his ideal university. Little F sincerely hopes that everyone will not make the same mistake again.

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$.

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 one line with $n$ space-separated non-negative integers, representing the distance from $s$ to each node.

For the sample explanation, please refer to [Template Problem with Random Data](https://www.luogu.com.cn/problem/P3371). 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