单源最短路

【题目描述】

给出$n$个点，$m$条无向边的简单图，求某点$s$到其他所有点的最短路。

【输入格式】

第1行三个正整数$n$，$m$，$s$（$n\leq 100$，$m\leq 500$，$s\leq n$）

下面$M$行，每行$3$个正整数$x, y, w$，为一条连接顶点$x$与$y$的边权值为$w$。($1\leq x,y\leq n$，$1\leq w\leq 1000$)

【输出格式】

包括$1$行，$n$个数，第$i$个数为点$s$到点$i$的最短路，第$s$个数应为$0$，数字之间空格隔开。

【样例输入】

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

【样例输出】

0 1 2 2 3

【来源】

改编自 福州NOIP2010培训Day5