『MGOI』Simple Round I | C. 魔法禁林

> 战斗的意义是为了生存，在这个竞争激烈的世界里，只有不断变强才能得以生存。——殿堂魔法士 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$。 | 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$ |