题目描述

Absurdistan 长期以来以骆驼商队闻名。新任大维齐尔决定迈向现代化：修建道路。

不过道路也不能修得太多，因此最终道路网必须保持最小，只要能够连接所有村庄即可。

前期勘察已经完成。对于某些村庄对，可以修建一条直接道路；对每条候选道路 $i$，已知其造价的下界 $l_i$ 与上界 $u_i$。

在你制定预算之后，每条候选道路的实际造价才会被确定。随后，建设者会在所有候选道路中选择总造价最小、且能够连接所有村庄的一组道路，也就是按实际造价求最小生成树。

假设每条道路的实际造价都是区间 $[l_i,u_i]$ 上独立均匀分布的实随机变量。

请计算最终最便宜道路网的期望总造价。

如果候选道路根本无法使所有村庄连通，则输出 -1。

输入格式

第一行一个整数 $T$，表示测试用例数。

每个测试用例前在原题格式中可能有一个空行。

每个测试用例第一行包含两个整数 $N,M$，分别表示村庄数和候选道路数。村庄编号为 $0,1,\ldots,N-1$。

接下来 $M$ 行，每行四个整数：

x_i y_i l_i u_i

表示可以在村庄 $x_i$ 与 $y_i$ 之间修建道路，其造价均匀分布于 $[l_i,u_i]$。

所有造价均为非负数。

输出格式

对每个测试用例输出一行。

若图无法连通，输出：

-1

否则输出最小生成树期望权值的最简分数：

A/B

即使 $B=1$，也必须输出分母。

样例输入

4
3 2
0 1 0 9
1 2 10 11

4 2
0 1 10 11
1 2 10 12

3 3
0 1 0 1
1 2 2 2
0 2 3 3

3 3
0 1 0 1
1 2 0 1
0 2 0 1

样例输出

15/1
-1
5/2
3/4

样例解释

第一组中两条道路都必须修建，其期望造价分别为 $9/2$ 与 $21/2$，总和为 $15$。

第二组中存在无法连接到其他村庄的点，因此答案为 -1。

第三组中无论随机造价如何，最便宜的两条边总是前两条，期望总造价为 $1/2+2=5/2$。

第四组的三条边都在 $[0,1]$ 上独立均匀分布，答案是三个随机数中较小两个之和的期望，即 $3/4$。