题目背景

通过了入门试炼之后，小舟终于登上了传说中的环岛。按规定，他要从岛的西端一路游览到东端，再从东端的渡口离开。环岛的风光实在太美，小舟玩了一趟还不过瘾，想乘摆渡船从东端回到西端再玩一趟。不过岛上有个规矩：想玩多少趟都行，但每一趟走的路线都不能和之前的完全相同。

题目描述

我们把环岛抽象成一个图，共 $n$ 个点代表岔路口，$m$ 条边表示路，边是有向的（只能沿着边的方向走），而且同一对点之间可能有多条边。输入保证这个图没有环，并且从西端到东端至少存在一条路线。两条路线被认为是不同的，当且仅当它们经过的路不完全相同。

你的任务是：把所有不同的路线全部游览一遍，一共要花多少时间？（注意：每相邻两趟之间都要花一次乘船返回的时间。）

输入格式

第一行为 $5$ 个整数 $n,m,s,t_0,t_1$，分别表示点数、边数、岛西端的编号、岛东端的编号（编号从 $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_0\leq 10^4$，$t_1\leq 10^4$。