Background

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

Problem Description

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.

Input Format

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 Format

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

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

Hint

[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$.

Translated by ChatGPT 5