在谱聚类（Spectral Clustering）中，数据点被表示为带权无向图 $G$ 的顶点。设 $n$ 和 $m$ 分别为图 $G$ 的顶点数和边数。顶点编号从 $1$ 到 $n$。较大的边权意味着相邻顶点非常相似；较小的边权则意味着不相似。聚类可以看作是将顶点划分为两个非空不相交的集合 $A$ 和 $B$，使得

$$Ncut(A, B) = \frac{cut(A, B)}{\sum_{x \in A} d_x} + \frac{cut(A, B)}{\sum_{x \in B} d_x}$$

最小化，其中 $cut(A, B)$ 是连接不同组顶点的边的总权重，$d_x$ 是与第 $x$ 个顶点相邻的边的总权重。

在本题中，给定一个具有 $n$ 个顶点和 $m$ 条边的图 $G$，其中每个顶点对应二维平面上的一个数据点。你需要找到一条直线，将这 $n$ 个点划分为两个非空集合 $A$ 和 $B$，使得 $Ncut(A, B)$ 最小化。注意，直线不能穿过任何数据点。

输入格式

输入包含多组数据。第一行包含一个整数 $T$ ($1 \le T \le 200$)，表示数据组数。

对于每组数据，第一行包含两个整数 $n$ 和 $m$ ($2 \le n \le 1\,500, n-1 \le m \le 5\,000$)，分别表示顶点数和边数。

接下来的 $n$ 行，第 $i$ 行包含两个整数 $x_i$ 和 $y_i$ ($1 \le i \le n, 0 \le x_i, y_i \le 10\,000$)，表示位于 $(x_i, y_i)$ 的数据点。保证没有两个点重合。

接下来的 $m$ 行，第 $i$ 行包含三个整数 $u_i, v_i$ 和 $w_i$ ($1 \le i \le m, 1 \le u_i, v_i \le n, u_i \neq v_i, 1 \le w_i \le 100$)，表示连接 $u_i$ 号顶点和 $v_i$ 号顶点的双向边。保证同一对顶点之间没有多条边，且图是连通的。

保证所有数据组的 $n$ 之和不超过 $1\,500$，所有数据组的 $m$ 之和不超过 $5\,000$。

输出格式

对于每组数据，输出一行，包含一个形如 $p/q$ 的既约分数，表示 $Ncut(A, B)$ 的最小值。形式上，你的答案必须满足 $p, q > 0$ 且 $\gcd(p, q) = 1$，其中 $\gcd(a, b)$ 表示 $a$ 和 $b$ 的最大公约数。

样例

样例输入 1

1
6 8
1 2
0 1
1 0
2 0
3 2
4 0
1 2 8
1 3 6
2 3 8
1 5 2
3 4 3
5 4 8
5 6 8
4 6 7

样例输出 1

500/2499

说明

以下是样例的最优解，如下图所示：

• $A = \{1, 2, 3\}, B = \{4, 5, 6\}$。
• $cut(A, B) = 2 + 3 = 5$。
• $\sum_{x \in A} d_x = d_1 + d_2 + d_3 = 16 + 16 + 17 = 49$。
• $\sum_{x \in B} d_x = d_4 + d_5 + d_6 = 18 + 18 + 15 = 51$。
• $Ncut(A, B) = \frac{5}{49} + \frac{5}{51} = \frac{500}{2499}$。

样例示意图。