【题目描述】

给定一个有n个点、m条有向边的非负权图，计算从点s出发，到每个点的最短路径长度（点的编号从1开始）。

【输入格式】

从文件path.in中读入数据。

第一行为三个整数n,m,s。

接下来的m行，每行三个整数u,v,w，表示从点u到v有一条边权为w的有向边。

【输出格式】

输出到文件path.out中。

输出一行n个整数，第i个表示s到第i个点的最短路径长度，若不能到达则输出-1。

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

【数据范围】