Untitled

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

int n, m;

vector<tuple<int, int, int>> in_MST;

struct DSU
{
    int n;
    vector<int> pa, sz;

    DSU(int n)
    {
        pa.resize(n + 1), sz.resize(n + 1);
        for (int i = 1; i <= n; i++)
            pa[i] = i;
    };

    int find_pa(int u);
    bool uni(int u, int v);
};

int DSU::find_pa(int u)
{
    return (pa[u] == u ? u : pa[u] = find_pa(u));
}

bool DSU::uni(int u, int v)
{
    int a = find_pa(u), b = find_pa(v);
    if (a == b)
        return 0;
    if (sz[a] > sz[b])
        swap(a, b);
    pa[a] = b;
    sz[b] += sz[a];
    return 1;
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> m;
    DSU dsu(n);
    vector<tuple<int, int, int>> E(m);
    for (auto &[a, b, c] : E)
    {
        cin >> a >> b >> c;
    }
    sort(E.begin(), E.end(), [](auto &a, auto &b)
         { return get<2>(a) < get<2>(b); });

    long long ans = 0;
    for (auto &[a, b, c] : E)
    {
        if (dsu.uni(a, b))
        {
            ans += c;
            in_MST.emplace_back(make_tuple(a, b, c));
        }
    }

    for (auto &[a, b, c] : in_MST)
    {
        long long g = 0;
        DSU dsu(n);
        for (auto &[u, v, w] : E)
        {
            if (a == u && b == v && c == w)
                continue;
            if (dsu.uni(u, v))
                g += w;
        }
        ans = min(ans, g);
    }

    cout << ans << '\n';
}