题目描述

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

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

输入格式

第一行为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

输出格式

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

样例数据

input

3 4 1 3 7

1 2 5

2 3 7

2 3 10

1 3 15

output

56

[样例说明]

共有3条路径可以从点1到点3，分别是1-2-3,1-2-3,1-3。时间计算为：

(5+7)+7 +(5+10)+7 +(15)=56

数据规模与约定

时间限制：$1 \text {s}$

空间限制：$256 \text {MB}$