1301. [HAOI 2006]旅行

【题目描述】

$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】

4 2
1 2 1
3 4 2
1 4

【样例输出1】

IMPOSSIBLE

【样例输入2】

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

【样例输出2】

5/4

【样例输入3】

3 2
1 2 2
2 3 4
1 3

【样例输出3】

2

【数据范围】

$1 <N \leq 500,1 <M \leq 5000$

$1 \leq x, y \leq N,0 < v < 3000,x \neq y$