题目描述

给定 \(N\) 个点 \(M\) 条边的有向图，请输出从某一点 \(S\) 出发到所有点的最短路径长度。

格式

输入格式

第 \(1\) 行包含三个整数 \(N,M,S\)，分别表示节点个数，有向边个数和出发点的编号。结点编号 \(1 \sim N\)。

以下 \(M\) 行，每行包含三个正整数 \(u,v,w\)，表示有一条从 \(u\) 至 \(v\) 的边,权值为 \(w（1≤w≤10000）\)。

输出格式

输出一行 \(N\) 个整数，第 \(i\) 个整数表示 \(S\) 到 \(i\) 的最短路径，如果无法到达，则输出 \(2^31-1\)（即 \(2147483647\)）。

样例1

输入样例1

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

输出样例1

0 2 4 3

限制

时间：\(1s\) 空间：\(256M\)

对于 \(100\%\) 的数据：\(1≤n≤10^5，1≤m≤10^6\)；

来源

地址：\(zloj,J2020\)域
作者：\(jialiang2509\)