UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#1928. Kthroad

统计 下载数据

Description

众所周知,在太阳系外围有一圈小行星带,而太阳系中离小行星带最近的Neptune往往面临着遭受小行星轰击的威胁。突然,某天Neptune上的天文台发现有一群小行星有k颗气势汹汹的袭来。作为Neptune的天文部长的小t想知道这些小行星分别要多久会撞到Neptune。你能够帮助他吗?
这些小行星的运行遵循以下一些规则:
1.     任意两颗小行星不会经过完全一样的路径,但有可能有绝大部分相同。
2.     对于某些小行星有可能受到其路径上的比较大的矮行星的引力作用,而围绕某个区域转圈。
3.     由于力的方向性,所以所有路径方向都是一定的。
4.     我们把空间中小行星可能经过的地方抽象成一个个点,并标号。共有N个点
5.     由于我们只关心其路径长度,所以并不给出这些点的具体坐标。
6.     两点间有可能有多条直接路径。任意两点间共有M条这样的路径。
7.     每课小行星在一个单位时间中会运动一个天文单位。且都会在当前的从起点到Neptune的最短路径上运行。
8.     每颗小行星对于我们来说都是一样的。
    请你编程求出所有小行星从起点(同一个起点)到达Neptune的所需花费的时间。
    

Input

第1行: 5个用空格隔开的整数:N、M、K、S、T,N个点M条边K个小行星, 起点的标号S,Neptune的标号T。
接下来M行每行3个大于0的整数,表示每条边的起点标号和终点标号以及这条边的长度。 
 

Output

共有K行每行一个整数,表示一颗小行星所要花费的时间。
 

Sample Input

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

Sample Output

4
4

Hint

数据约定N<= 10000, M <= 500000, K <= 100

对于所有数据在给定的数据范围内阶梯增长。

Source