#Psp11. 【例题1】单源最短路径

【例题1】单源最短路径

【例题1】单源最短路径

题目描述

给定一个n个点,m条有向边的带非负权图,请你计算从s出发,到每个点的距离。

数据保证你能从s出发到任意点。

输入格式

第一行为三个正整数n,m,s。接下来m行,每行三个非负整数ui,vi,wi,表示从ui到vi有一条权值为wiu_i,v_i,w_i,表示从u_i到v_i有一条权值为w_i的有向边。

输出格式

输出一行n个空格分隔的非负整数,表示s到每个点的距离。

数据范围

(原站未提供,导入后需人工补齐)

样例

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

提示

对于100%的数据,$1<=n<=10^5,1<=m<=2*10^5,s=1,1<=u_i,v_i<=n,0<=w_i<=10^9$,0<=∑\sum wi<=109w_i<=10^9。