题目描述

城市中有 $n$ 个配送站，编号为 $1$ 到 $n$。总部设在 $s$ 号站，需要分别向每个站发送一份急件。

站点之间有 $m$ 条单向运输线路。每条线路给出起点 $u$、终点 $v$ 和运输时间 $w$。急件可以在站点立即转运，转运本身不耗时。每份急件独立选择路线，不考虑车辆数量或线路拥堵。

请计算从总部到每个站点所需的最短时间；无法到达的站点输出 $-1$。总部到自身的时间为 $0$。

输入格式

第一行三个整数 $n,m,s$，表示站点数、线路数和总部编号。

接下来 $m$ 行，每行三个整数 $u,v,w$，表示一条从 $u$ 到 $v$ 的单向线路，耗时为 $w$。

输出格式

输出一行 $n$ 个整数，第 $i$ 个整数表示总部到 $i$ 号站的最短时间，整数之间以一个空格分隔。

样例 1

5 6 1
1 2 6
1 3 2
3 2 1
2 4 4
3 4 8
5 1 1

0 3 2 7 -1

样例 2

1 0 1

0

样例解释

样例1：从1号站到2号站，经过3号站耗时为2+1=3，比直达更短；到4号站的最短时间为2+1+4=7。5号站虽然有通往1号站的线路，但从1号站无法到达5号站。

样例2：唯一的站点就是总部，无需运输，答案为0。

数据范围与约定

全部数据满足：$1\le n\le 100000$，$0\le m\le 200000$，$1\le s\le n$；$1\le u,v\le n$，$u\ne v$，$0\le w\le 10^9$。

允许同向重边，允许零耗时线路；不保证所有站点均能从总部到达。单向线路不能反向使用。时间均为整数，答案可能超过32位有符号整数范围。

时间限制：2000ms；内存限制：256m。