#include<bits/stdc++.h>
using namespace std;
int f[1010][1010],n,m,F[1010][1010];
int main(){
	cin>>n>>m;
	memset(f,-1,sizeof(f));
//	memset(F,0x3f,sizeof(F));
	for(int i=1;i<=m;i++){
		int x,y,w;
		cin>>x>>y>>w;
		f[x][y]=f[y][x]=w;
	}
	long long ans=2e9,sum=0;
	//==================
	for(int k=1;k<=n;k++){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				if(f[i][k]!=-1&&f[k][j]!=-1)
				if(f[i][j]>f[i][k]+f[k][j]&&i!=j&&j!=k&&i!=k||f[i][j]==-1){
					f[i][j]=f[i][k]+f[k][j];
				}
			}
			
		}
	}
	
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			for(int a=1;a<=n;a++)
				for(int b=1;b<=n;b++)
					F[a][b]=f[a][b];
			F[i][j]=F[j][i]=0;
			for(int a=1;a<=n;a++)
				for(int b=1;b<=n;b++)
					if(F[a][b]>F[a][i]+F[i][b]&&a!=b&&a!=i&&b!=i||F[a][b]==-1)
						F[a][b]=F[a][i]+F[i][b];
			for(int a=1;a<=n;a++)
				for(int b=1;b<=n;b++)
					if(F[a][b]>F[a][j]+F[j][b]&&a!=b&&a!=j&&b!=j||F[a][b]==-1)
						F[a][b]=F[a][j]+F[j][b];
			sum=0;
			for(int a=1;a<=n;a++){
				for(int b=a+1;b<=n;b++){
					sum+=F[a][b];
				}
			}
			ans=min(ans,sum);			
		}
	}
/*	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cout<<F[i][j]<<" ";
		}
		cout<<endl;
	}*/

	cout<<sum;
}