Submission

Score: 0

User: mantaggez

Problemset: รัฐบาล

Language: cpp

Time: 0.002 second

Submitted On: 2026-03-12 15:01:59

#include <bits/stdc++.h>

using namespace std;
using pii = pair<int, int>;
using tup = tuple<int, int, int>;

const int nx = 105;
const int INF = 1e9;

int n, m, dsu[nx], d1 = INF, d2 = INF;
vector<tup> edge, bad;

int find(int x)
{
    if(dsu[x] == x) return x;
    dsu[x] = find(dsu[x]);
    return dsu[x];
}

int MST(tup e)
{
    int sum = 0;
    auto [bw, bu, bv] = e;
    iota(dsu, dsu + nx, 0);
    for(auto& [w, u, v] : edge)
    {
        int pu = find(u), pv = find(v);
        if(w == bw && bu == u && bv == v) continue;
        if(pu != pv)
        {
            dsu[pu] = pv;
            sum += w;
            if(bw == -1 && bu == -1 && bv == -1) bad.push_back({w, u, v});
        }
    }
    return sum;
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin >> n >> m;
    for(int i=0;i<m;i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        edge.push_back({w, u, v});
    }

    sort(edge.begin(), edge.end());

    d1 = MST({-1, -1, -1});
    for(auto& [w, u, v] : bad) d2 = min(d2, MST({w, u, v}));
    
    cout << d1 << ' ' << d2 ;
    
    return 0;
}