B. 最大价值
time limit per test
5 s
memory limit per test
512 megabytes
input
standard input
output
standard output

你是蔬菜大学 XCPC 集训队的一名队员。

蔬菜大学的 XCPC 集训室可以抽象成 $$$n$$$ 个点 $$$m$$$ 条边的无向图。门所在的点为 $$$S$$$，而你的座位位于 $$$T$$$。

一天，你带着价值为 $$$k$$$ 的外卖走进了集训室。你发现集训室的每条边上都有一名饥肠辘辘的队员在游荡。具体来说，边 $$$i$$$ 有边权 $$$w_i$$$，表示对应队员的饱食度。如果你走过这条边时候手上外卖价值不高于 $$$w_i$$$，那么这名队员不会理你。否则，他会开始食用你的外卖，直至你手中外卖价值恰好剩余 $$$w_i$$$ 时候才会放你走。

你不能将一部分外卖暂存至某个点，因为暂存的部分会在你离开该点后离奇地消失。你想知道，从 $$$S$$$ 出发并到达 $$$T$$$ 时你手中最多剩余多少价值的外卖。

Input

第一行五个整数 $$$n,m,S,T,k$$$，含义如题面所示，保证 $$$S$$$ 和 $$$T$$$ 不同。

接下来 $$$m$$$ 行每行三个整数 $$$u,v,w$$$ 描述每条边，分别表示两个端点和边权。

$$$2\le n\le10^6,1\le m\le10^6, 0 \le k\le10^9,0\le w\le10^9$$$

Output

一个整数，代表最多能带到 $$$T$$$ 点的外卖价值。如果 $$$S$$$ 不可达 $$$T$$$，则认为是 0

Example
Input
4 5 1 4 6
1 2 1
1 4 2
1 3 3
2 4 3
3 4 1
Output
2