P3371 [Template] Single-Source Shortest Path (Weakened Version)

The testdata for this problem is random. In exams, there may be adversarial testdata that makes SPFA fail; if needed, please refer to [P4779](https://www.luogu.org/problemnew/show/P4779).

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

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

- 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](https://www.luogu.org/problemnew/show/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