#include<bits/stdc++.h>
using namespace std;
int n,m,f[105][105],ans=2e9,g[105][105];
int main()
{
	cin>>n>>m;
	memset(f,63,sizeof(f));
	for(int i=1;i<=m;i++)
	{
		int x,y,w;
		scanf("%d%d%d",&x,&y,&w);
		f[x][y]=w;f[y][x]=w;
	}
	for(int k=1;k<=n;k++)
	 for(int i=1;i<=n;i++)
	  for(int j=1;j<=n;j++)
	   if(i!=j&&j!=k&&i!=k)
	    if(f[i][j]>f[i][k]+f[k][j])
	     f[i][j]=f[i][k]+f[k][j],g[i][j]=f[i][j];
	for(int i=1;i<=n;i++)
	 for(int j=1;j<i;j++)
	 {
	 	f[i][j]=f[j][i]=0;
	 	for(int k1=1;k1<=n;k1++)
	 	 for(int k2=1;k2<=n;k2++)
	 	  f[k1][k2]=min(f[k1][k2],f[k1][i]+f[i][k2]);
	 	for(int k1=1;k1<=n;k1++)
	 	 for(int k2=1;k2<=n;k2++)
	 	  f[k1][k2]=min(f[k1][k2],f[k1][j]+f[j][k2]);
	 	
	 	int res=0;
	 	for(int k1=1;k1<=n;k1++)
	 	 for(int k2=1;k2<k1;k2++)
	 	  res+=f[k1][k2];
	 	ans=min(ans,res);
	 	
	 	for(int k1=1;k1<=n;k1++)
	 	 for(int k2=1;k2<=n;k2++)
	 	  f[k1][k2]=g[k1][k2];
	 }
	cout<<ans;
	return 0;
}