#include<cstdio>
using namespace std;
const int MAXN=105,INF=0x3f3f3f3f;
int g[MAXN][MAXN],t[MAXN][MAXN];
int floyd(int n) {
  for(int i=1;i<=n;i++) {
  	for(int j=1;j<=n;j++) {
  	  for(int k=1;k<=n;k++) {
  	  	if(g[j][i]!=INF&&g[i][k]!=INF&&g[j][i]+g[i][k]<g[j][k])
  	  	  g[j][k]=g[j][i]+g[i][k];
  	  }
  	}
  }
  int ans=INF;
  for(int i=1;i<=n;i++) {
  	for(int j=i+1;j<=n;j++) {
  	  for(int k=1;k<=n;k++) {
  	  	for(int l=1;l<=n;l++)
  	  	  t[k][l]=g[k][l];
  	  }
  	  t[i][j]=t[j][i]=0;
  	  for(int k=1;k<=n;k++) {
  	  	for(int l=1;l<=n;l++) {
  	  	  if(t[k][i]!=INF&&t[i][l]!=INF&&t[k][i]+t[i][l]<t[k][l])
  	  	    t[k][l]=t[k][i]+t[i][l];
  	  	}
  	  }
  	  for(int k=1;k<=n;k++) {
  	  	for(int l=1;l<=n;l++) {
  	  	  if(t[k][j]!=INF&&t[j][l]!=INF&&t[k][j]+t[j][l]<t[k][l])
  	  	    t[k][l]=t[k][j]+t[j][l];
  	  	}
  	  }
  	}
  	int sum=0;
  	for(int k=1;k<=n;k++) {
  	  for(int l=k+1;l<=n;l++)
  	    sum+=t[k][l];
  	}
  	if(sum<ans)
  	  ans=sum;
  }
  return ans;
}
int main() {
  int n,m;
  scanf("%d %d",&n,&m);
  for(int i=1;i<=n;i++) {
  	for(int j=1;j<=n;j++) {
  	  if(i!=j)
  	    g[i][j]=INF;
  	}
  }
  for(int i=1,u,v,w;i<=m;i++) {
  	scanf("%d %d %d",&u,&v,&w);
  	if(g[u][v]>w)
  	  g[u][v]=w;
  	if(g[v][u]>w)
  	  g[v][u]=w;
  }
  printf("%d",floyd(n));
  return 0;
}