There are n islands in the archipelago. The KTO focuses on the synergy effect created when some islands are selected for a tour belt. Synergy effects are assigned to several pairs of islands. A synergy effect SE(u, v) or SE(v, u) between two islands u and v is a positive integer which represents a value anticipated when both u and v are included in a tour belt. The KTO wants to select two or more islands for the tour belt so that the economic benefit of the tour belt is as high as possible.

To be precise, we define a connected graph G = (V, E), where V is a set of n vertices and E is a set of m edges. Each vertex of V represents an island in the archipelago, and an edge (u, v) of E exists if a synergy effect SE(u, v) is defined between two distinct vertices (islands) u and v of V. Let A be a subset consisting of at least two vertices in V. An edge (u, v) is an inside edge of A if both u and v are in A. An edge (u, v) is a border edge of A if one of u and v is in A and the other is not in A.

A vertex set B of a connected subgraph of G with 2| B|n is called a candidate for the tour belt if the synergy effect of every inside edge of B is larger than the synergy effect of any border edge of B. A candiate will be chosen as the final tour belt by the KTO. There can be many possible candidates in G. Note that V itself is a candidate because there are no border edges. The graph in Figure 1(a) has three candidates {1,2}, {3,4} and {1,2,3,4}, but {2,3,4} is not a candidate because there are inside edges whose synergy effects are not larger than those of some border edges. The graph in Figure 1(b) contains six candidates, {1,2}, {3,4}, {5,6}, {7,8}, {3,4,5,6} and {1,2,3,4,5,6,7,8}. But {1,2,7,8} is not a candidate because it does not form a connected subgraph of G, i.e., there are no edges connecting {1,2} and {7,8}.

The KTO will decide one candidate in G as the final tour belt. For this, the KTO asks you to find all candidates in G. You write a program to print the sum of the sizes of all candidates in a given graph G. For example, the graph in Figure 1(a) contains three candidates and the sum of their sizes is 2 + 2 + 4 = 8, and the graph in Figure 1(b) contains six candidates and the sum of their sizes is 2 + 2 + 2 + 2 + 4 + 8 = 20.

Input 

Your program is to read input from standard input. The input consists of T test cases. The number of test cases T is given in the first line of the input. Each test case starts with a line containing two integers n ( 2n5, 000) and m ( 1m), where n represents the number of vertices (islands) and m represents the number of edges of a connected graph G. Islands are numbered from 1 to n. In the following m lines, the synergy effects assigned to m edges are given; each line contains three integers, u, v, and k ( 1uvn, 1k10⁵), where k is the synergy effect between two distinct islands u and v, i.e., SE(u, v) = SE(u, v) = k.

Output 

Your program is to write to standard output. Print exactly one line for each test case. Print the sum of the sizes of all candidates for a test case.

The following shows sample input and output for two test cases.

Sample Input 

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

Sample Output 

8
20

不可能窮舉所有 s 的情況去進行檢查，因此考慮最小生成樹的思路。

而這裡相反，將權重大的先放入，根據 Kruskal 的想法逐一放入。

每放一次就進行檢查，之所以這麼做是為了要保證集合內部的權重的最小值盡可能地大於連外的所有權重，

那麼最大的那個點會被放進來，但他所造成影響可能會那條邊更小，對於其他相同情況的點不會影響。

因為題目要求的是 <, 而不是 <=，所以是可以允許的，在邏輯上不會有錯誤。

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
struct E {
    int x, y, v;
    bool operator<(const E &a) const {
        return v > a.v;
    }
};
E D[1250000];
vector<int> g[5005];
int p[5005], rank[5005];//disjoint set.
int findp(int x) {
    return p[x] == x ? x : (p[x]=findp(p[x]));
}
int joint(int x, int y) {
    x = findp(x), y = findp(y);
    if(x == y)  return 0;
    if(rank[x] > rank[y])
        rank[x] += rank[y], p[y] = x;
    else
        rank[y] += rank[x], p[x] = y;
    return 1;
}
int check(int x, int n) {//divide s-t set
    int smn = 0xfffff, tmx = 0;
    int i, j, y, pp, e;
    E edge;
    x = findp(x);
    for(i = 1; i <= n; i++) {
        pp = findp(i);
        if(pp != x) continue;
        // find a set {s}
        for(j = 0; j < g[i].size(); j++) {
            e = g[i][j];
            edge = D[e];
            if(edge.x != i)
                pp = findp(edge.x);
            else
                pp = findp(edge.y);
            if(pp == x) //same {s}
                smn = min(smn, edge.v);
            else
                tmx = max(tmx, edge.v);
        }
        if(smn < tmx)   return false;
    }
    return smn > tmx;
}
void MST(int n, int m) {//max spanning tree
    int ret = 0, i, j;
    for(i = 1; i <= n; i++)
        p[i] = i, rank[i] = 1;
    sort(D, D+m);
    for(i = 0; i < m; i++) {
        g[D[i].x].push_back(i);
        g[D[i].y].push_back(i);
    }
    for(i = 0; i < m; i++) {
        if(joint(D[i].x, D[i].y)) {
            if(check(D[i].x, n))
                ret += rank[findp(D[i].x)];
        }
    }
    printf("%d\n", ret);
}
int main() {
    int testcase, n, m, i;
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d %d", &n, &m);
        for(i = 1; i <= n; i++)
            g[i].clear();
        for(i = 0; i < m; i++)
            scanf("%d %d %d", &D[i].x, &D[i].y, &D[i].v);
        MST(n, m);
    }
    return 0;
}