极限卡常，84分

#include<bits/stdc++.h>
#define int long long
#define maxn 100+10
#define inf 0x3f3f3f3f

using namespace std;

int n,m;
int g[maxn][maxn];
int f[maxn][maxn];
int ans=INT_MAX;

inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}

inline int floyd(){
	for(register int i=1;i<=n;i++) for(register int j=1;j<=n;j++) f[i][j]=g[i][j];
	for(register int k=1;k<=n;k++){
		for(register int i=1;i<=n;i++){
			for(register int j=1;j<=n;j++){
				f[i][j]=min(f[i][k]+f[k][j],f[i][j]);
			}
		}
	}
	int cnt=0;
	for(register int i=1;i<=n;i++){
		for(register int j=1;j<=i;j++){
			cnt+=f[i][j];
		}
	}
	return cnt;
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	n=read(),m=read();
	for(register int i=1;i<=n;i++) for(register int j=1;j<=n;j++){
		if(i==j) g[i][j]=0;
		else g[i][j]=inf;
	}
	for(register int i=1;i<=m;i++){
		int x,y,w;
		x=read(),y=read(),w=read();
		g[x][y]=min(g[x][y],w);
		g[y][x]=min(g[y][x],w);
//		f[x][y]=min(f[x][y],w);
//		f[y][x]=min(f[y][x],w);
	}
//	ans=floyd();
	for(register int i=1;i<=n;i++){
		for(register int j=i+1;j<=n;j++){
			if(g[i][j]!=0){
				int t=g[i][j];
				g[i][j]=g[j][i]=0;
				ans=min(ans,floyd());
				g[i][j]=g[j][i]=t;
			}
		}
	}
	printf("%lld\n",ans);
	return 0;
}