#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
#include<algorithm>
#define Maxn 300010
#define maxn 300005
using namespace std;
#define ll long long
struct edge{
int to,w,nxt;
}edge[Maxn];
int head[Maxn/],tot;
void addedge(int a,int b,int c){
edge[tot].to=b;
edge[tot].w=c;
edge[tot].nxt=head[a];
head[a]=tot++;
}
struct line{
int u,v,w;
bool operator<(const line &a)const{
return w<a.w;
}
}q[Maxn]; int vis[Maxn];
int fa[Maxn/];
int findset(int x){
return fa[x]==x?x:(fa[x]=findset(fa[x]));
}
int unionset(int a,int b){
return fa[findset(a)]=findset(b);
}
ll d[maxn],f[maxn][],dp[maxn][][];//dp[i][j][0|1]用来表示向上倍增的最大边,严格次大边
void bfs(){
queue<int>q;
q.push();
d[]=;
while(!q.empty()){
int x=q.front();q.pop();
for(int i=head[x];i!=-;i=edge[i].nxt){
int y=edge[i].to;
if(d[y])continue;
d[y]=d[x]+;
f[y][]=x;
dp[y][][]=edge[i].w;
dp[y][][]=-0x3f3f3f3f;
for(int k=;k<=;k++){
f[y][k]=f[f[y][k-]][k-];
int a=dp[y][k-][];//y向上下一半的最大值
int b=dp[y][k-][];//y向上下一半的严格次大值
int c=dp[f[y][k-]][k-][];//y向上上一半的最大值
int d=dp[f[y][k-]][k-][];//y向上上一半的严格次大值
dp[y][k][]=max(a,c);
if(a==c)dp[x][k][]=max(b,d);
else if(a>c)dp[x][k][]=max(c,b);
else if(a<c)dp[x][k][]=max(a,d);
}
q.push(y);
}
}
}
inline void calc(ll &val1,ll &val2,ll a,ll b){//更新最大和次大
if(a<=val1)val2=max(a,val2);
else val2=val1,val1=a;
}
int lca(int x,int y,int z){//处理加入(x,y,z)后的次小生成树
ll val1=-,val2=-;
if(d[x]<d[y])swap(x,y);
for(int i=;i>=;i--)
if(d[f[x][i]]>=d[y]){
calc(val1,val2,dp[x][i][],dp[x][i][]);
x=f[x][i];
}
if(x==y){
if(val1!=z)return val1;
return val2;
} for(int i=;i>=;i--)
if(f[x][i]!=f[y][i]){
calc(val1,val2,dp[x][i][],dp[x][i][]);
calc(val1,val2,dp[y][i][],dp[y][i][]);
x=f[x][i],y=f[y][i];
}
calc(val1,val2,dp[x][][],dp[x][][]);
calc(val1,val2,dp[y][][],dp[y][][]);
x=f[x][];
if(val1!=z)return val1;
else return val2;
} int main(){
int n,m;
scanf("%d%d",&n,&m);
for(int i=;i<m;i++)
scanf("%d%d%d",&q[i].u,&q[i].v,&q[i].w);
sort(q,q+m);
for(int i=;i<=n;i++) fa[i]=i;
memset(head,-,sizeof head);
memset(vis,,sizeof vis);
tot=;
int cnt=;
long long ans=;
for(int i=;i<m;i++){
int u=q[i].u,v=q[i].v;
if(findset(u)==findset(v)) continue;
unionset(u,v);
vis[i]=;
addedge(u,v,q[i].w);
addedge(v,u,q[i].w);
ans+=q[i].w;
if(++cnt==n-) break;
}
bfs();
int z=0x3f3f3f3f;
for(int i=;i<m;i++)
if(!vis[i]) {
int t=lca(q[i].u,q[i].v,q[i].w);
if(t>)z=min(z,-t+q[i].w);
}
printf("%lld\n",ans+z);
return ;
}
05-06 04:05