给定一张 $n$ 个点 $m$ 条边的带权有向图，求起点 $s$ 到所有点的最短路。
输入格式
第一行三个由空格隔开的整数 $ n $、$ m $、$ s $。
之后的 $ m $ 行，每行三个正整数 $ s_i $、$ t_i $、$w_i$ ($1 \le s_i, t_i \le n$, $0 \leq w_i \leq 10 ^ 9$) ，表示一条从 $ s_i $ 到 $ t_i $ 长度为 $ w_i $ 的有向边。图中可能存在重边或自环。
输出格式
输出一行，包含 $n$ 整数 $d_1, d_2, \ldots, d_n$。其中 $d_i$ 表示从 $s$ 到 $i$ 的最短路长度。如果不存在对应的道路，则输出 $-1$。
样例数据
样例 1 输入
4 5 1
1 2 1000
2 3 10000
3 1 1
3 4 100000
3 4 1000000样例 1 输出
0 1000 11000 111000样例 2 输入
2 1 2
1 2 1样例 2 输出
-1 0子任务
对于所有数据，$1 \le n \le 3 \cdot 10^5$，$0 \le m \le 10^6$。