#include<cstdio>
#include<vector>
#include<algorithm>

using namespace std;

struct edge {
    int u,v,w;
    edge() {}
    edge(int a, int b, int c) : u(a), v(b), w(c) {}
    bool operator < (const edge &rhs) const {
        return w < rhs.w;
    }
} E[250005];

int p[555],r[555];
vector<int> set[555];
vector<int> adj[555];
vector<int> wht[555];
int T,n,m;

int find(int u) {
    if(u == p[u]) return u;
    else return p[u] = find(p[u]);
}

void unite(int u, int v) {
    int x = find(u), y = find(v);
    if(x == y) return;

    if(r[x] >= r[y]) {
        p[y] = x, r[x] += r[y];
        for(int i=0;i<set[y].size();++i) set[x].push_back(set[y][i]);
        r[y] = 0, set[y].clear();
    }
    else if(r[x] < r[y]) {
        p[x] = y, r[y] += r[x];
        for(int i=0;i<set[x].size();++i) set[y].push_back(set[x][i]);
        r[x] = 0, set[x].clear();
    }
}

bool ck(int root) {
    int mn = 1000000, mx = 0;
    for(int i=0;i<set[root].size();++i) {
        int u =set[root][i];
        for(int j=0;j<adj[u].size();++j) {
            int v = adj[u][j];
            if(root == find(v)) mn = min(mn, wht[u][j]);
            else mx = max(mx, wht[u][j]);
            if(mx >= mn) return 0;
        }
    } return 1;
}

int main() {
#ifdef LOCAL
    freopen("in.txt","r",stdin);
#endif
    scanf("%d",&T);
    while(T--) {
        scanf("%d%d",&n,&m);
        for(int i=0;i<m;++i) {
            int u,v,w; scanf("%d%d%d",&u,&v,&w), u--, v--;
            E[i] = edge(u,v,w);
            adj[u].push_back(v);
            wht[u].push_back(w);
            adj[v].push_back(u);
            wht[v].push_back(w);
        } sort(E, E + m);

        for(int i=0;i<n;++i) p[i] = i, r[i] = 1, set[i].push_back(i);

        long long ans = 0;
        for(int i=m-1;i>=0;--i) {
            int x = find(E[i].u), y = find(E[i].v);
            if(x == y) continue;
            unite(x, y);
            x = find(x);
            if(ck(x)) ans += r[x];
        } printf("%lld\n",ans);

        for(int i=0;i<n;++i) adj[i].clear(), wht[i].clear(), set[i].clear();
    }
}

위의 소스 풀이는 유니온파인드 이용해서 그리디하게 하는 풀이인데요, 문제 정의에 n = 5000으로 정해져있는데 저 풀이가 최악의 경우 n^3풀이라 당연히 tle를 예상하고 제출했는데 매우 빠른 시간안에 억쎕이 뜨더라구요.. 좀 이상해서 n 사이즈를 500으로 잡고 재제출을 해도 런타임 에러 대신 억쎕이 뜨더군요..
원래 대회에선 사이즈가 500이었나요? 아님 n^3이 아닌 다른 풀이가 있는건가요? 일단 live archive 온라인 졎지에서는 데이터 자체를 500으로만 만들어논거같네요;

문제 링크:https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=382&page=show_problem&problem=2849