开学的第一天，小 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 初始时需要的最小生命值。
## Input
第一行四个整数 $n,m,s,t$。
接下来 $m$ 行，每行三个整数 $u,v,w$，表示编号为 $u
,v$ 的点之间有一条边，边上魔兽的攻击力为 $w$。
## Output
一行一个整数，表示小 M 初始时需要的最小生命值。
[samples]
## Background
> 战斗的意义是为了生存，在这个竞争激烈的世界里，只有不断变强才能得以生存。——殿堂魔法士 S
## Note
**【样例 1 解释】**
初始时，小 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 初始时需要的最小生命值。
**【数据范围】**
**本题采用 Subtask 捆绑测试。**
对于所有数据，$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$。
| Subtask | $n$ | $m$ | $w\le$ | 分值 |
| :------------: | :----------: | :----------: | :-----------: | :----------------:|
| $1$ | $5$ | $10$ | $10$ | $11$ |
| $2$ | $2000$ | $4000$ | $10$ | $27$ |
| $3$ | $20000$ | $40000$ | $1$ | $19$ |
| $4$ | $20000$ | $40000$ | $100$ | $43$ |