P2502 [HAOI2006] Travel

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.

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.

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.

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