P9504 "MGOI" Simple Round I | C. Forbidden Forest of Magic.

> The meaning of battle is to survive. In this highly competitive world, only by becoming stronger can you survive. — Hall Magician S.

On the first day of school, Little M cannot wait to plan a trip to the mysterious Forbidden Forest. Little M has two important attributes: mana and health. Very specially, at the beginning, these two values can be chosen **arbitrarily** by Little M. The Forbidden Forest can be seen as an undirected simple connected graph with $n$ vertices and $m$ edges. Little M will walk in the forest, from the start vertex $s$ to $t$. Each time he traverses an edge, Little M’s **mana** decreases by $1$. At the same time, there is a magical beast with an attack attribute on each edge, and Little M must fight it. If Little M’s mana before traversing this edge is $k$, and the beast’s attack on this edge is $w$, then the battle that happens while traversing this edge will consume $\left\lfloor \dfrac{w}{k} \right\rfloor$ **health**. The beast will not be defeated, so **if the same edge is traversed multiple times, a battle will happen every time**. **Little M must ensure that when his mana is fully used up, his health is $0$, and at that moment he has arrived at vertex $t$.** You need to find the minimum initial health Little M needs.

The first line contains four integers $n, m, s, t$. The next $m$ lines each contain three integers $u, v, w$, indicating that there is an edge between vertices $u, v$, and the beast’s attack on this edge is $w$.

Output one integer in one line, representing the minimum initial health Little M needs.

**[Sample 1 Explanation]** At the beginning, Little M chooses mana $2$ and health $4$. - $1\rightarrow2$: mana left $1$, health left $4 - \left\lfloor \frac{2}{2} \right\rfloor=3$. - $2\rightarrow3$: mana left $0$, health left $3 - \left\lfloor \frac{3}{1} \right\rfloor=0$. It can be proven that $4$ is the minimum initial health Little M needs. **[Constraints]** **This problem uses bundled Subtask testdata.** For all testdata, $1 \le n \le 20000$, $1 \le m \le 40000$, $1\le s,t,u,v\le n$, $s\ne t$, the graph is an undirected simple connected graph, and $0\le w\le 100$. | Subtask | $n$ | $m$ | $w\le$ | Score | | :------------: | :----------: | :----------: | :-----------: | :----------------:| | $1$ | $5$ | $10$ | $10$ | $11$ | | $2$ | $2000$ | $4000$ | $10$ | $27$ | | $3$ | $20000$ | $40000$ | $1$ | $19$ | | $4$ | $20000$ | $40000$ | $100$ | $43$ | Translated by ChatGPT 5