Problem5713--最舒适的路线

5713: 最舒适的路线

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 256 MiB

Description

异形卵潜伏在某区域的一个神经网络中。其网络共有 $N$ 个神经元(编号为 $1,\ 2,\ \dots,\ N$),这些神经元由 $M$ 条通道连接着。两个神经元之间可能有多条通道。异形卵可以在这些通道上来回游动,但在神经网络中任一条通道的游动速度必须是一定的。当然异形卵不希望从一条通道游动到另一条通道速度变化太大,否则它会很不舒服。
现在异形卵聚居在神经元 $S$ 点,想游动到神经元 $T$ 点。它希望选择一条游动过程中通道最大速度与最小速度比尽可能小的路线,也就是所谓最舒适的路线。

Input

第一行: $K$ 表示有多少组测试数据。 
接下来对每组测试数据:
第 $1$ 行包括两个整数 $N,\ M$。
第 $2$~$M+1$ 行:$X_i\ Y_i\ V_i$。表示神经元 $X_i$ 到神经元 $Y_i$ 之间通道的速度必须是 $V_i$。
最后一行:$S\ T$。

Output

对于每组测试数据,输出一行:如果神经元 $S$ 到神经元 $T$ 没有路线,输出 ${IMPOSSIBLE}$。否则输出一个数,表示最小的速度比。如果需要,输出一个既约分数。

Constraints

$2≤K≤5$
$1<N≤500$
$0<M≤5000$
$1≤ X_i,\ Y_i,\ S,\ T ≤N$
$0< V_i <30000$
$V_i$ 是整数。

Sample 1 Input

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

Sample 1 Output

2
5/4

Source/Category