A569.单源最短路径1

给出一个可能有重边的有向图，请输出从某一点出发到所有点的最短路径长度。

第一行输入三个整数 $n,m,s$，分别表示顶点数、有向边数和出发顶点编号。

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

输出一行 $n$ 个整数，第 $i$ 个整数表示 $s$ 到顶点 $i$ 的最短距离；不能到达时输出 $-1$。

数据范围

$1\le n\le10^6$，$1\le m\le2\times10^6$，$1\le s,u,v\le n$，$1\le w\le10^9$。允许重边。