rt,

WA on sub1 #1.

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 100007, M = 300007, inf = 0x7f7f7f7f7f7f7f7f;

struct edge
{
	int nxt, to, val;
}e[N << 1];
int h[N], cnt;

void add(int u, int v, int w)
{
	e[++ cnt].nxt = h[u], e[cnt].to = v, e[cnt].val = w, h[u] = cnt;
}

struct edge1
{
	int u, v, w;
	bool used;
}e1[M];

int n, m, fa[N], ans0;

bool cmp(edge1 a, edge1 b)
{
	return a.w < b.w;
}

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

void kruskal()
{
	sort(e1 + 1, e1 + m + 1, cmp);
	for (int i = 1 ; i <= m ; i ++)
	{
		int u = find(e1[i].u), v = find(e1[i].v);
		if (u == v) continue;
		ans0 += e1[i].w;
		add(e1[i].u, e1[i].v, e1[i].w);
		add(e1[i].v, e1[i].u, e1[i].w);
		e1[i].used = 1, fa[v] = u;
	}
}

int f[N][20], mx[N][20], mx2[N][20], dep[N];

void dfs(int u)
{
	dep[u] = dep[f[u][0]] + 1;
	for (int i = 1 ; i <= 18 ; i ++)
	{
		f[u][i] = f[f[u][i - 1]][i - 1];
		if (mx[u][i - 1] == mx[f[u][i - 1]][i - 1])
		{
			mx[u][i] = mx[u][i - 1];
			mx2[u][i] = max(mx2[f[u][i - 1]][i - 1], mx2[u][i - 1]);
		}
		if (mx[u][i - 1] > mx[f[u][i - 1]][i - 1])
		{
			mx[u][i] = mx[u][i - 1];
			mx2[u][i] = max(mx[f[u][i - 1]][i - 1], mx2[f[u][i - 1]][i - 1]);
		}
		if (mx[f[u][i - 1]][i - 1] > mx[u][i - 1])
		{
			mx[u][i] = mx[f[u][i - 1]][i - 1];
			mx2[u][i] = max(mx[u][i - 1], mx2[f[u][i - 1]][i - 1]);
		}
	}
	for (int i = h[u] ; i ; i = e[i].nxt)
	{
		int v = e[i].to, w = e[i].val;
		if (v == f[u][0]) continue;
		f[v][0] = u, mx[v][0] = w;
		dfs(v);
	}
}

int lca(int u, int v)
{
	if (dep[u] < dep[v]) swap(u, v);
	for (int i = 18 ; i >= 0 ; i --)
		if (dep[u] - dep[v] >= (1 << i))
			u = f[u][i];
	if (u == v) return u;
	for (int i = 18 ; i >= 0 ; i --)
		if (f[u][i] != f[v][i])
			u = f[u][i], v = f[v][i];
	return f[u][0];
}

int cal(int u, int v, int w)
{
	int l = lca(u, v);
	int nmx = 0, nmx2 = 0;
	for (int i = 18 ; i >= 0 ; i --)
	{
		if (dep[f[u][i]] >= dep[l])
		{
			if (nmx == mx[u][i]) nmx2 = max(mx2[u][i], nmx2);
			if (nmx > mx[u][i]) nmx2 = max(mx[u][i], nmx2);
			if (nmx < mx[u][i]) nmx2 = max(mx2[u][i], nmx), nmx = mx[u][i]; 
			u = f[u][i];
		}
		if (dep[f[v][i]] >= dep[l])
		{
			if (nmx == mx[v][i]) nmx2 = max(mx2[v][i], nmx2);
			if (nmx > mx[v][i]) nmx2 = max(mx[v][i], nmx2);
			if (nmx < mx[v][i]) nmx2 = max(mx2[v][i], nmx), nmx = mx[v][i];
			v = f[v][i];
		}
	}
	if (w != nmx) return ans0 - nmx + w;
	if (nmx2) return ans0 - nmx2 + w;
	return inf;
}

signed main()
{
	cin >> n >> m;
	for (int i = 1 ; i <= m ; i ++) cin >> e1[i].u >> e1[i].v >> e1[i].w;
	for (int i = 1 ; i <= n ; i ++) fa[i] = i;
	kruskal();
	dfs(1);
	int ans = inf;
	for (int i = 1 ; i <= m ; i ++)
		if (!e1[i].used)
			ans = min(cal(e1[i].u, e1[i].v, e1[i].w), ans);
	cout << ans;
    return 0;
}