You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

战斗的意义是为了生存，在这个竞争激烈的世界里，只有不断变强才能得以生存。——殿堂魔法士 S

题目描述

开学的第一天，小 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 初始时需要的最小生命值。

3 3 1 3
1 2 2
1 3 5
3 2 3

4

5 10 1 5
2 1 3
3 1 7
4 2 4
5 3 9
5 1 7
2 3 2
5 4 6
1 4 10
5 2 5
3 4 10

6

提示

【样例 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$。