O(mlogm+nlogn)
int p[N]; //并查集
int h[N], e[M], ne[M], w[M], idx; //memset(h, -1, sizeof h);
int depth[N], fa[N][20], d1[N][20], d2[N][20];
struct Edge
{
int a, b, w;
bool used;
bool operator<(const Edge &W) const
{
return w < W.w;
}
} edge[M];
void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
int find(int x) //并查集
{
if (p[x] != x)
{
p[x] = find(p[x]);
}
return p[x];
}
ll kruskal() //连通时返回最小生成树边权和,否则返回INF(0x3f3f3f3f)
{
sort(edge, edge + m);
for (int i = 1; i <= n; i++)
{
p[i] = i;
}
ll res = 0;
for (int i = 0; i < m; i++)
{
int a = find(edge[i].a), b = find(edge[i].b);
if (a != b)
{
p[a] = b;
res += edge[i].w;
edge[i].used = 1;
}
}
return res;
}
void build()
{
memset(h, -1, sizeof h);
for (int i = 0; i < m; i++)
{
if (edge[i].used)
{
int a = edge[i].a, b = edge[i].b, w = edge[i].w;
add(a, b, w), add(b, a, w);
}
}
}
void bfs(int root)
{
depth[root] = 1;
queue<int> q;
q.push(root);
while (q.size())
{
int u = q.front();
q.pop();
for (int i = h[u]; ~i; i = ne[i])
{
int v = e[i];
if (depth[v])
{
continue;
}
depth[v] = depth[u] + 1;
d1[v][0] = w[i], d2[v][0] = -INF;
q.push(v);
fa[v][0] = u;
for (int k = 1; k <= 16; k++)
{
int anc = fa[v][k - 1];
fa[v][k] = fa[anc][k - 1];
int distance[4] = {d1[v][k - 1], d2[v][k - 1], d1[anc][k - 1], d2[anc][k - 1]};
d1[v][k] = d2[v][k] = -INF;
for (int j = 0; j < 4; j++)
{
int d = distance[j];
if (d > d1[v][k])
{
d2[v][k] = d1[v][k];
d1[v][k] = d;
}
else if (d != d1[v][k] && d > d2[v][k])
{
d2[v][k] = d;
}
}
}
}
}
}
int lca(int a, int b, int w)
{
static int distance[200];
int cnt = 0;
if (depth[a] < depth[b])
{
swap(a, b);
}
for (int k = 16; k >= 0; k--)
{
if (depth[fa[a][k]] >= depth[b])
{
distance[cnt++] = d1[a][k];
distance[cnt++] = d2[a][k];
a = fa[a][k];
}
}
if (a != b)
{
for (int k = 16; k >= 0; k--)
if (fa[a][k] != fa[b][k])
{
distance[cnt++] = d1[a][k];
distance[cnt++] = d2[a][k];
distance[cnt++] = d1[b][k];
distance[cnt++] = d2[b][k];
a = fa[a][k], b = fa[b][k];
}
distance[cnt++] = d1[a][0];
distance[cnt++] = d1[b][0];
}
int dist1 = -INF, dist2 = -INF;
for (int i = 0; i < cnt; i++)
{
int d = distance[i];
if (d > dist1)
{
dist2 = dist1, dist1 = d;
}
else if (d != dist1 && d > dist2)
{
dist2 = d;
}
}
if (w > dist1)
{
return w - dist1;
}
if (w > dist2)
{
return w - dist2;
}
return INF;
}
int main()
{
std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
cin >> n >> m;
for (int i = 0; i < m; i++)
{
cin >> edge[i].a >> edge[i].b >> edge[i].w;
}
ll sum = kruskal();
build();
bfs(1);
ll res = 1e18;
for (int i = 0; i < m; i++)
{
if (!edge[i].used)
{
int a = edge[i].a, b = edge[i].b, w = edge[i].w;
res = min(res, sum + lca(a, b, w));
}
}
cout << res << endl;
return 0;
}