题目描述

给出一个带权无向图，与一个数字 $x$，输出图中有多少无序点对 $(s,t)$ 使得 $MinCut(s,t)\le x$。

$MinCut$ 是指 $s$ 和 $t$ 之间的最小割，即，删去边权之和尽量少的边，使 $s$ 和 $t$ 不连通时最小的边权之和。

输入格式

本题包含多组数据。

第一行一个整数 $T$，表示数据组数。

对于每组数据，第一行两个整数 $n,m$，分别表示点数和边数。

接下来 $m$ 行，每行三个数 $u,v,w$，表示 $u,v$ 之间有一条权为 $w$ 的边。

输出格式

每组数据的输出应该由 $q$ 行组成，每个 $q$ 行中有一个整数，表示与该查询对应的无序 $(s,t)$ 对的数量。

在数据之间输出一个空行。

样例

这里仅提供一组小数据，大样例将在题目附件中给出。

6 9
1 2 1
1 3 7
2 3 1
2 4 3
2 5 2
3 5 4
4 5 1
4 6 6
5 6 2
1
6

12

数据规模与约定

对于所有数据，$1\le T\le 20,1\le n\le 1500,1\le m\le 3000$。