Preparing NOJ

H神秘岛

1000ms 65536K

Description:

FireDancer来到一个神秘岛,他要从岛的西头到东头然后在东头的码头离开。可是当他走了一次后,发现这个岛的景色非常的美丽,于是他从东头的传送门传到了西头,换了一种走法又走了一遍。发现还不过瘾,又走了一遍……终于,FireDancer把所有的从西头到东头的路径都走了一遍。他站在岛东头的海滩上,突然想到了一个问题,那就是他一共花了多少时间。他把这个问题交给了你。

FireDancer把这个岛抽象成了一个图,共n个点代表路的相交处,m条边表示路,边是有向的(只能按照边的方向行走),且可能有连接相同两点的边。输入保证这个图没有环,而且从西头到东头至少存在一条路径。两条路径被认为是不同的当且仅当它们所经过的路不完全相同。


Input:

第一行为5个整数,n、m、s、t、t0,分别表示点数,边数,岛西头的编号,岛东头的编号和传送一次的时间(编号是从1到n)。以后m行,每行3个整数,x、y、t,表示从点x到点y有一条行走耗时为t的路。2<=n<=10000; 1<=m<=50000;t<=10000;t0<=10000


Output:

若总耗时为total,则输出total mod 10000(total对10000取余)。


Sample Input:

3 4 1 3 7
1 2 5
2 3 7
2 3 10
1 3 15

Sample Output:

56

Note:

 

本题由旧版NOJ导入,来源:NUAA_柏楠

Info

NOJ

Provider NOJ

Code NOJ1175

Tags

Submitted 0

Passed 0

AC Rate 0%

Date 04/20/2019 10:03:10

Related

Nothing Yet