题解

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Edge {
    int u, v;
    long long w;
    bool operator<(const Edge& other) const {
        return w < other.w;
    }
};

vector<int> parent;

int find(int u) {
    if (parent[u] != u) {
        parent[u] = find(parent[u]);
    }
    return parent[u];
}

bool unite(int u, int v) {
    u = find(u);
    v = find(v);
    if (u == v) return false;
    parent[v] = u;
    return true;
}

void solve() {
    int N, M;
    long long p;
    cin >> N >> M >> p;
    vector<Edge> edges(M);
    for (int i = 0; i < M; ++i) {
        cin >> edges[i].u >> edges[i].v >> edges[i].w;
        edges[i].u--;
        edges[i].v--;
    }
    
    parent.resize(N);
    for (int i = 0; i < N; ++i) {
        parent[i] = i;
    }
    
    sort(edges.begin(), edges.end());
    
    long long mst_cost = 0;
    int edges_used = 0;
    vector<bool> in_mst(M, false);
    
    for (int i = 0; i < M; ++i) {
        if (unite(edges[i].u, edges[i].v)) {
            mst_cost += edges[i].w;
            in_mst[i] = true;
            edges_used++;
        }
    }
    
    if (edges_used != N - 1) {
        cout << "NO" << endl;
        return;
    }
    
    if (mst_cost > p) {
        cout << "NO" << endl;
        return;
    }
    
    long long current_sum = mst_cost;
    int additional_edges = 0;
    
    for (int i = 0; i < M; ++i) {
        if (!in_mst[i]) {
            if (current_sum + edges[i].w <= p) {
                current_sum += edges[i].w;
                additional_edges++;
            } else {
                break;
            }
        }
    }
    
    int total_edges_kept = (N - 1) + additional_edges;
    int min_removed = M - total_edges_kept;
    cout << min_removed << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int T;
    cin >> T;
    while (T--) {
        solve();
    }
    
    return 0;
}