题目描述

顺利通过了黄药师的考验，下面就可以尽情游览桃花岛了！

你要从桃花岛的西头开始一直玩到东头，然后在东头的码头离开。可是当你游玩了一次后，发现桃花岛的景色实在是非常的美丽！！！于是你还想乘船从桃花岛东头的码头回到西头，再玩一遍，但是桃花岛有个规矩：你可以游览无数遍，但是每次游玩的路线不能完全一样。

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

你的任务是：把所有不同的路线游览完一共要花多少时间？

输入格式

第一行为 $5$ 个整数 $n,m,s,t,t_0$，分别表示点数，边数，岛西头的编号，岛东头的编号（编号是从 $1$ 到 $n$）和你乘船从岛东头到西头一次的时间。

以下 $m$ 行，每行 $3$ 个整数 $x,y,t$，表示从点 $x$ 到点 $y$ 有一条行走耗时为 $t$ 的路。

每一行的多个数据之间用一个空格隔开。

输出格式

假设总耗时为 $total$，则输出 $total\ \bmod 10000$ 的值（$total$ 对 $10000$ 取余）。

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$

数据范围

$2\leq n\leq 10^4$，$1\leq m\leq 5\times 10^4$，$t\leq 10^4$，$t_0\leq 10^4$。