FireDancer 来到一个神秘岛，他要从岛的西头到东头然后在东头的码头离开。可是当他走了一次后，发现这个岛的景色非常的美丽，于是他从东头的传送门传到了西头，换了一种走法又走了一遍。发现还不过瘾，又走了一遍……终于，FireDancer 把所有的从西头到东头的路径都走了一遍。他站在岛东头的海滩上，突然想到了一个问题，那就是他一共花了多少时间。他把这个问题交给了你。
FireDancer 把这个岛抽象成了一个图，共 n 个点代表路的相交处，m 条边表示路，边是有向的（只能按照边的方向行走），且可能有连接相同两点的边。输入保证这个图没有环，而且从西头到东头至少存在一条路径。两条路径被认为是不同的当且仅当它们所经过的路不完全相同。
输入数据共若干行。
第 1 行为 5 个整数，n(2<=n<=10,000)、m(1<=m<=50,000)、s、 t、t0(t0<=10,000)，分别表示点数，边数，岛西头的编号，岛东头的编号和传送一次的时间（编号是从 1 到 n）。
接下来 m 行，每行 3 个整数，x、y、t (t<=10,000)，表示从点 x 到点 y 有一条行走耗时为 t 的路。
输出数据仅一个整数。若总耗时为 total，则输出的值为 total mod 10,000。
3 4 1 3 7
1 2 5
2 3 7
2 3 10
1 3 15 56共有 3条路径可以从点 1到点 3，分别是 1-2-3,1 -2-3和 1-3。时间计算为： (5+7 )+7+(5+10 )+7+(15)=56
江苏省苏州中学 NOIP 复赛训练题 2012