P2502 [HAOI2006] 旅行

题目描述

Z 小镇是一个景色宜人的地方，吸引来自各地的观光客来此旅游观光。Z 小镇附近共有 $n$ 个景点（编号为 $1,2,3,\ldots,n$），这些景点被 $m$ 条道路连接着，所有道路都是双向的，两个景点之间可能有多条道路。

也许是为了保护该地的旅游资源，Z 小镇有个奇怪的规定，就是对于一条给定的公路 $r_i$，任何在该公路上行驶的车辆速度必须为 $v_i$。

速度变化太快使得游客们很不舒服，因此从一个景点前往另一个景点的时候，大家都希望选择行驶过程中最大速度和最小速度的比尽可能小的路线，也就是所谓最舒适的路线。

输入格式

第一行包含两个正整数 $n,m$。

接下来的 $m$ 行每行包含三个正整数 $x,y,v$。表示景点 $x$ 到景点 $y$ 之间有一条双向公路，车辆必须以速度 $v$ 在该公路上行驶。

最后一行包含两个正整数 $s,t$，表示想知道从景点 $s$ 到景点 $t$ 最大最小速度比最小的路径。$s$ 和 $t$ 不可能相同。

输出格式

如果景点 $s$ 到景点 $t$ 没有路径，输出 IMPOSSIBLE。否则输出一个数，表示最小的速度比。如果需要，输出一个既约分数。

输入输出样例 #1

输入 #1

4 2
1 2 1
3 4 2
1 4

输出 #1

IMPOSSIBLE

输入输出样例 #2

输入 #2

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

输出 #2

5/4

输入输出样例 #3

输入 #3

3 2
1 2 2
2 3 4
1 3

输出 #3

2

说明/提示

对于 $100\%$ 的数据，$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$。