Description

As stated, given a directed graph, output the shortest path length from a specified vertex to every vertex.

Input Format

The first line contains three integers $n, m, s$, denoting the number of vertices, the number of directed edges, and the index of the source vertex.

Each of the next $m$ lines contains three integers $u, v, w$, denoting a directed edge $u \to v$ with length $w$.

Output Format

Output $n$ integers on one line. The $i$-th integer is the shortest path distance from $s$ to vertex $i$. If a vertex is unreachable, output $2^{31} - 1$.

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

• Constraints
  For $20\%$ of the testdata: $1 \le n \le 5$, $1 \le m \le 15$;
  For $40\%$ of the testdata: $1 \le n \le 100$, $1 \le m \le 10^4$;
  For $70\%$ of the testdata: $1 \le n \le 1000$, $1 \le m \le 10^5$;
  For $100\%$ of the testdata: $1 \le n \le 10^4$, $1 \le m \le 5 \times 10^5$, $1 \le u, v \le n$, $w \ge 0$, $\sum w < 2^{31}$; the testdata is guaranteed to be random.

• Update 2022/07/29: There may be multiple edges between two vertices. Please take note.

• For the full $100\%$ testdata, please refer to P4779. Note that its constraints differ slightly from this problem.

Sample note:

In the image, the text positions for "1 to 3" and "1 to 4" are swapped.

Translated by ChatGPT 5