#pragma GCC optimize("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize ("Ofast,no-stack-protector", "omit-frame-pointer", "inline", "-ffast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.2,fma,popcnt,abm,mmx,avx")

#include<bits/stdc++.h>

#define ll long long
#define pp push_back
#define endl '\n'
#define all(x) x.begin(),x.end()
#define ld long double
#define PI acos(-1)
#define sin(a) sin((a)*PI/180)
#define cos(a) cos((a)*PI/180)
#define ones(x) __builtin_popcountll(x)
//#define int ll

using namespace std;

void Drakon() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef Clion
    freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout);
#endif
}

unsigned long long inf = 1e10;
const double EPS = 1e-6;
const int MOD = 1000000007, N = 200005, LOG = 25;

ll mul(const ll &a, const ll &b) {
    return (a % MOD + MOD) * (b % MOD + MOD) % MOD;
}

ll add(const ll &a, const ll &b) {
    return (a + b + 2 * MOD) % MOD;
}

ll pw(ll x, ll y) {
    ll ret = 1;
    while (y > 0) {
        if (y % 2 == 0) {
            x = mul(x, x);
            y = y / 2;
        } else {
            ret = mul(ret, x);
            y = y - 1;
        }
    }
    return ret;
}

struct DSU {
    vector<int>par, sz;

    DSU(int n) : par(n), sz(n, 1) { iota(par.begin(), par.end(), 0); }

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

    bool join(int x, int y){
        x = find(x);
        y = find(y);
        if(x == y)return false;
        if(sz[x] < sz[y])
            swap(x, y);
        sz[x] += sz[y];
        par[y] = x;
        return true;
    }
};

vector<pair<int, pair<int, int>>>edges;
vector<pair<int, int>>adj[N];
int depth[N], up[N][LOG], n, m, timer, tin[N], tout[N];


void dfs(int u, int p) {
    tin[u] = timer++;
    for (auto v: adj[u]) {
        if (v.first == p)continue;
        depth[v.first] = depth[u] + 1;
        up[v.first][0] = u;
        dfs(v.first, u);
    }
    tout[u] = timer - 1;
}

int LCA(int u, int v) {
    if (depth[u] < depth[v])
        swap(u, v);
    int k = depth[u] - depth[v];
    for (int i = 0; i < LOG; ++i) {
        if ((1 << i) & k) {
            u = up[u][i];
        }
    }
    if (u == v)
        return u;
    for (int i = LOG - 1; i >= 0; --i) {
        if (up[u][i] != up[v][i]) {
            u = up[u][i];
            v = up[v][i];
        }
    }
    return up[u][0];
}

void build() {
    dfs(0, 0);
    for (int j = 1; j < LOG; ++j) {
        for (int i = 0; i < n; ++i) {
            up[i][j] = up[up[i][j - 1]][j - 1];
        }
    }
}

map<int, int>toAdd[N], toRemove[N];
ll mx;

void calc(int u, int p, int w){

    for(auto v : adj[u]){
        if(v.first == p)continue;
        calc(v.first, u, v.second);
        if(toAdd[v.first].size() > toAdd[u].size())swap(toAdd[v.first], toAdd[u]);
        for(auto x : toAdd[v.first])toAdd[u][x.first] += x.second;
        toAdd[v.first].clear();
    }

    for(auto x : toRemove[u]){
        toAdd[u][x.first] -= x.second * 2;
        if(!toAdd[u][x.first])toAdd[u].erase(x.first);
    }
    toRemove[u].clear();
    
    if(!toAdd[u].empty() && u){
        mx = max(mx, 1ll * toAdd[u].begin() -> first - w);
    }
    
}

void solve() {
    cin >> n >> m;

    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        u--,v--;
        edges.push_back({w, {u, v}});
    }

    sort(all(edges));
    DSU dsu(n);
    ll ans = 0;
    vector<bool>vis(m);
    for (int i = 0; i < m; ++i) {
        int u = edges[i].second.first, v = edges[i].second.second;
        if(dsu.join(u, v)){
            adj[u].pp({v, edges[i].first});
            adj[v].pp({u, edges[i].first});
            ans += edges[i].first;
            vis[i] = true;
        }
    }

    build();

    for (int i = 0; i < m; ++i) {
        if(vis[i])continue;
        int u = edges[i].second.first, v = edges[i].second.second, w = edges[i].first;
        toAdd[u][w] ++;
        toAdd[v][w] ++;
        toRemove[LCA(u, v)][w] ++;
    }

    calc(0, 0, 0);
    cout << ans + mx;
}

signed main() {
    Drakon();
    int t = 1;
    //cin >> t;
    while (t--) {
        solve();
    }
}

In file included from /usr/include/c++/13/string:43,
                 from /usr/include/c++/13/bitset:52,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:52,
                 from answer.code:6:
/usr/include/c++/13/bits/allocator.h: In destructor ‘std::_Vector_base<std::pair<int, std::pair<int, int> >, std::allocator<std::pair<int, std::pair<int, int> > > >::_Vector_impl::~_Vector_impl()’:
/usr/include/c++/13/bits/allocator.h:184:7: error: inlining failed in call to ‘always_inline’ ‘std::allocator< <template-parameter-1-1> >::~allocator() noexcept [with _Tp = std::pair<int, std::pair<int, int> >]’: target specific option mismatch
  184 |       ~allocator() _GLIBCXX_NOTHROW { }
      |       ^
In file included from /usr/include/c++/13/vector:66,
                 from /usr/include/c++/13/functional:64,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:53:
/usr/include/c++/13/bits/stl_vector.h:133:14: note: called from here
  133 |       struct _Vector_impl
      |              ^~~~~~~~~~~~