【模板】单源最短路径(弱化版)

题目背景

本题数据更为合理

题目描述

如题,给出一个有向图,请输出从某一点出发到所有点的最短路径长度。

输入输出格式

输入格式


第一行包含三个整数$N$、$M$、$S$,分别表示点的个数、有向边的个数、出发点的编号。 接下来$M$行每行包含三个整数$Fi$、$Gi$、$Wi$,分别表示第$i$条有向边的出发点、目标点和长度。

输出格式


一行,包含N个用空格分隔的整数,其中第i个整数表示从点S出发到点i的最短路径长度(若$S=i$则最短路径长度为$0$,若从点S无法到达点i,则输出$2147483647$)

输入输出样例

输入样例 #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

说明

对于10%的数据:$N<=10$,$M<=20$,$Wi<=500$。 对于50%的数据:$N<=2000$,$M<=5000$,$Wi<=50000$。 对于100%的数据:$N<=10000$,$M<=100000$,$Wi<=500000$。不存在负环。