本题总用时为各测试点用时最大值。

这是一道模板题。

给定一张边权非负的有向图（可能存在重边自环），请求出点 $S$ 到点 $1\sim n$ 的最短路长度。

输入格式

第一行三个个正整数 $n,m,S$，表示图中点数，边数，源点编号。

下面 $m$ 行，每行三个整数 $u_i,v_i,w_i$，表示存在一条 $u_i$ 到达 $v_i$，边权为 $w_i$ 的边。

输出格式

一行 $n$ 个整数，表示 $S$ 点到每个点的最短路大小，若无法到达，则输出 -1。

样例一

input

5 10 1
3 4 2
2 3 4
1 2 1
2 4 2
4 5 8
5 2 10
4 2 7
3 3 10
2 2 1
3 2 1

output

0 1 5 3 11

限制与约定

对于所有数据，满足：

$1\le u_i,v_i,S\le n$, $1\le n\le 3\times {10}^5$, $1\le m\le {10}^6$, $0\le w_i\le {10}^9$。

时间限制：$2\mathtt{\text{s}}$

空间限制：$512\mathtt{\text{MB}}$

下载

样例数据下载