Description

Z Town is a picturesque place that attracts tourists from all over. There are $n$ scenic spots near Z Town (numbered $1, 2, 3, \ldots, n$), connected by $m$ roads. All roads are bidirectional, and there may be multiple roads between two spots.

Perhaps to protect local tourism resources, Z Town has a peculiar rule: for a given road $r_i$, any vehicle traveling on that road must have speed $v_i$.

Frequent speed changes make tourists uncomfortable, so when traveling from one spot to another, everyone wants to choose a route that minimizes the ratio between the maximum and minimum speeds during the trip, i.e., the most comfortable route.

Input Format

The first line contains two positive integers $n, m$.

Each of the next $m$ lines contains three positive integers $x, y, v$. This means there is a bidirectional road between spots $x$ and $y$, and vehicles must travel at speed $v$ on that road.

The last line contains two positive integers $s, t$, asking for the path from spot $s$ to spot $t$ with the smallest ratio of maximum to minimum speeds. $s$ and $t$ are not the same.

Output Format

If there is no path from $s$ to $t$, output IMPOSSIBLE. Otherwise, output a number representing the minimal speed ratio. If necessary, output a reduced fraction.

4 2
1 2 1
3 4 2
1 4

IMPOSSIBLE

3 3
1 2 10
1 2 5
2 3 8
1 3

5/4

3 2
1 2 2
2 3 4
1 3

2

Hint

For $100\%$ of the testdata, $1 \le x, y \le n \le 500$, $1 \le v < 3 \times 10^4$, $1 \le m \le 5 \times 10^3$, $x \ne y$.

Translated by ChatGPT 5