You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

【题目描述】

给定一个有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

【数据范围】