开学的第一天，小 M 迫不及待地计划着前往神秘的禁林。

小 M 拥有两个重要的属性，魔力值和生命值。非常特别的是，初始时，这两个值可以由小 M 任意决定。

禁林可以看作一张 $n$ 个点 $m$ 条边的无向简单连通图。小 M 将在禁林里面行走，从起点 $s$ 走到 $t$。

每经过一条边，小 M 的魔力值都会减去 1。同时，每条边上有一个具有攻击力属性的魔兽，小 M 要与之战斗。若小 M 经过这条边之前的魔力值为 $k$，这条边上魔兽的攻击力为 $w$，那么经过这条边时发生的战斗将会消耗 $\left\lfloor \dfrac{w}{k} \right\rfloor$ 的生命值。魔兽不会被打败，因此多次经过同一条边，每次都会发生战斗。

小 M 需要保证，当他的魔力值消耗完时，他的生命值为 0，且此时走到 $t$ 点。

你需要求出小 M 初始时需要的最小生命值。

第一行四个整数 $n,m,s,t$。

接下来 $m$ 行，每行三个整数 $u,v,w$，表示编号为 $u,v$ 的点之间有一条边，边上魔兽的攻击力为 $w$。

一行一个整数，表示小 M 初始时需要的最小生命值。

对于所有数据，$1 \le n \le 20000$，$1 \le m \le 40000$，$1\le s,t,u,v\le n$，$s\ne t$，图为无向简单连通图，$0\le w\le 100$。

4

初始时，小 M 选择魔力值为 $2$，生命值为 $4$。

- $1\rightarrow2$：魔力值剩余 $1$，生命值剩余 $4 - \left\lfloor \frac{2}{2} \right\rfloor=3$。
- $2\rightarrow3$：魔力值剩余 $0$，生命值剩余 $3 - \left\lfloor \frac{3}{1} \right\rfloor=0$。

可以证明 $4$ 为小 M 初始时需要的最小生命值。