SP3900 MCQUERY - MinCut Query

[English](/problems/MCQUERY/en/) [Vietnamese](/problems/MCQUERY/vn/)You are given a weighted undirected graph with edge weight denoting the capacity of the edge. Now given a number x, output how many unordered (s,t) pairs are there in the graph such that minCut(s,t)

First line contains T, the number of test cases. For each test case the first line contains two integers n and m, denoting the number of vertices and the number of edges in the graph. Next m lines contain 3 integers u,v,c denoting an undirected of capacity c between vertices u and v; 1

The output for each test case should consist of q lines with one integers in each of them denoting the number of unordered (s,t) pairs corresponding to that query. Output a blank line BETWEEN the test cases. Note: The timelimit for the problem is somewhat strict.