题目描述

Farmer John 有 N 个农场，编号为 1 ~ N。

有 M 条双向通行的道路。每条道路连接两个不同的农场（无自环）。两个农场之间可能有多条道路（可能有重边）。每条道路有一个长度。

Bessie 正在 A 号农场，她要去往 B 号农场。在路途中，她可以多次重复经过同一个农场，也可以多次重复经过同一条道路。她可能有多条行走路线。对于某一条路线，将该路线上经过的最长的那条道路的长度（记为 Mx）与最短的那条道路的长度（记为 Mi）的比值 Mx/Mi 作为衡量该条路线的一个指标。Bessie 希望找到指标值最小的那条路线，她认为这样的路线是最优路线。

你能帮助她吗？你只需要输出最优路线的指标值（即 Mx/Mi 的值）。

输入格式

第一行：两个整数 N, M;

接下来 M 行：每行三个整数 u, v, w, 表示 u 号农场和 v 号农场之间有一条长度为 w 的双向道路。

第 M + 2 行：两个整数 A, B。

输出格式

如果找不到通行路线，输出 -1；否则输出最优路线的指标值即 Mx/Mi 的值的最简分数形式。若最简分数的分母为 1，则只输出分子。

4 2
1 2 3
3 4 5
2 3

-1

3 3
1 2 6
1 2 1
2 3 4
1 3

3/2

3 2
1 2 3
3 2 1
1 3

3

数据范围

100% 的数据：$1 ≤ N ≤ 500, 1 ≤ M ≤ 5000, 1 ≤ u, v ≤ N，1 ≤ w < 30000，u ≠ v, A ≠ B$。