题目描述

给定一个 $n$ 个点， $m$ 条边的有向图，请你计算从源点 $s$ 出发，到每个点的最短路径长度。

输入格式

第一行三个整数 $n,m,s$ ，表示点数、边数和源点。

接下来 $m$ 行，每行三个整数 $u,v,w$，表示从 $u$ 到 $v$ 有一条长度为 $w$ 的有向边。

输出格式

一行 $n$ 个整数，第 $i$ 个整数表示从源点 $s$ 到点 $i$ 的最短路径长度，特殊地，如果不能到达，输出 $-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

数据范围

$$\begin{aligned} & \bullet \ 2 \le n \le 10^5\\ & \bullet \ 1 \le m \le 2 \times 10^5\\ & \bullet \ 0 \le w_i \le 10^9 \\ & \bullet \ 1 \le u_i,v_i \le n\\& 不含重边和自环 \end{aligned}$$