93pts wa on #5 玄关求条

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define usd unsigned
#define el cout << '\n'
#define lowbit(x) (x & (-x))
const int ranmod = 1e7;
#define random ((rand() * rand()) % ranmod)
#define AC return 
#define AK return 0
#define YS cout << "YES"
#define NO cout << "NO"
#define Ys cout << "Yes"
#define No cout << "No"
#define ys cout << "yes"
#define no cout << "no"
#define ls(i) ch[i][0]
#define rs(i) ch[i][1]
#define debug(num) cerr << #num << ' ' << num << '\n'
#define pii pair <int, int> 
// void init();
void main_();
signed main() {
	ios :: sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	// freopen(".in", "r", stdin);
	// freopen(".out", "w", stdout);
	int t = 1;
	// cin >> t;
	while(t--) {
		// init();
		main_();
	}
	AK;
}
const int mod = 95225987, maxn = 3 * 1e5 + 18;

int n, m, ans = 0, answer = 1e18, dp[maxn][33], nxt[maxn][33], dep[maxn];
bool used[maxn];
vector <pii> vec[maxn];

int fa[maxn];
int find(int x) {
    if(fa[x] == x) return x;
    else {
        fa[x] = find(fa[x]);
        return fa[x];
    }
}
void merge(int a, int b) {
    fa[find(a)] = fa[find(b)];
}

struct edge {
    int u, v, w;
}e[maxn];
bool operator <(edge a, edge b) {
    return a.w < b.w;
}

void dfs(int x, int from, int w) {
    dep[x] = dep[from] + 1;
    nxt[x][0] = from, dp[x][0] = w;
    for(int i = 1; i <= 30; i++) {
        nxt[x][i] = nxt[nxt[x][i - 1]][i - 1];
        dp[x][i] = max(dp[x][i - 1], dp[nxt[x][i - 1]][i - 1]);
    }
    for(auto tmp : vec[x]) {
        int to = tmp.first, ww = tmp.second;
        if(to == from) continue;
        dfs(to, x, ww);
    }
}

int lca(int u, int v, int pos) {
    if(u == v) return 0;
    int res = -1;
    if(dep[u] > dep[v]) swap(u, v); // dep[u] < dep[v]
    if(dep[u] != dep[v]) {
        for(int i = 30; i >= 0; i--) if(dep[u] <= dep[nxt[v][i]]) {
            if(dp[v][i] < pos) res = max(res, dp[v][i]);
            v = nxt[v][i];
        }
    }
    if(u == v) AC res;
    for(int i = 30; i >= 0; i--) {
        if(nxt[u][i] != nxt[v][i]) {
            if(dp[v][i] < pos) res = max(res, dp[v][i]); 
            if(dp[u][i] < pos) res = max(res, dp[u][i]); 
            u = nxt[u][i], v = nxt[v][i];
        }
    }
    if(dp[u][0] < pos) res = max(res, dp[u][0]);
    if(dp[v][0] < pos) res = max(res, dp[v][0]);
    return res;
}

void main_() {
	cin >> n >> m;
    for(int i = 1; i <= n; i++) fa[i] = i;
    for(int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        if(v > u) swap(u, v); // u < v
        e[i].u = u, e[i].v = v, e[i].w = w;
    }
    sort(e + 1, e + m + 1);
    int cnt = 0;
    for(int i = 1; i <= m; i++) {
        int u, v, w;
        u = e[i].u, v = e[i].v, w = e[i].w;
        if(find(u) == find(v)) continue;
        ans += w;
        merge(u, v);
        vec[u].push_back({v, w});
        vec[v].push_back({u, w});
        used[i] = true;
        cnt++;
        if(cnt == n - 1) break;
    }
    // debug(1);
    // dep[0] = 0;
    dfs(1, 1, 0);
    for(int i = 1; i <= m; i++) {
        if(used[i] || e[i].v == e[i].u) continue;
        int cur = lca(e[i].u, e[i].v, e[i].w), tmp = e[i].w - cur;
        debug(tmp), debug(cur);
        if(tmp != 0 && cur != -1) answer = min(answer, tmp);
    }
    // debug(ans);
    cout << ans + answer; el;
}