Untitled

int n, m;
 
struct edge
{
    int u, v, cost;
    bool operator<(const edge &other) const
    {
        return cost < other.cost;
    }
};
 
vii parent;
 
void make_set(int u)
{
    parent[u] = u;
}
 
int find_set(int v)
{
    return v == parent[v] ? v : parent[v] = find_set(parent[v]);
}
 
void union_set(int u, int v)
{
    u = find_set(u);
    v = find_set(v);
    if(u == v) return;
    parent[u] = v;
}
 
pair<int, vii> kruskal(int n, vector<edge> &e, sii &ex)
{
    parent.assign(n + 1, 0);
    FORD(i, 1, n)
    {
        make_set(i);
    }
    int total = 0, e_cnt = 0;
    vii mst;
    FOR(i, 0, e.size())
    {
        if(ex.count(i)) continue;
        if(find_set(e[i].u) != find_set(e[i].v))
        {
            union_set(e[i].u, e[i].v);
            total += e[i].cost;
            mst.pb(i);
            ++e_cnt;
        }
    }
    return (e_cnt == n - 1) ? make_pair(total, mst) : make_pair(INT_MAX, vii());
}
 
void nhap()
{
    cin >> n >> m;
}
 
void solve()
{
    nhap();
    vector<edge> e(m);
    FOR(i, 0, m)
    {
        cin >> e[i].u >> e[i].v >> e[i].cost;
    }
    sort(all(e));
    sii ex;
    pair<int, vii> res = kruskal(n, e, ex);
    int s1 = res.fi;
    vii mst = res.se;
    int s2 = INT_MAX;
    for(int i : mst)
    {
        ex.clear();
        ex.insert(i);
        int cost = kruskal(n, e, ex).fi;
        if(cost != INT_MAX)
        {
            s2 = min(s2, cost);
        }
    }
    cout << s1 << " " << s2;
}