#include<cstdio>
#include<iostream>
using namespace std;
#define re register
#define li(i,j,k) for(int i=j ; i<=k ; i++)
#define si(i,j,k) for(int i=j ; i>=k ; i--)
#define ll long long
const int INF=2147483647;
int n,m;
int dis[1001][1001];
inline int read(){
	re int x=0;re int f=1;
	char ch=getchar();
	while(ch<'0' || ch>'9'){
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(ch>='0' && ch<='9'){
		x=(x<<3)+(x<<1)+ch-'0';
		ch=getchar();
	}
	return x;
}
int min(int a,int b){
	return a<b?a:b;
}
int main(){
	scanf("%d%d",&n,&m);
	for(re int i=1 ; i<=n ; i++){
		for(re int j=1 ; j<=n ; j++){
			dis[i][j]=INF;
		}
	}
	for(re int i=1 ; i<=m ; i++){
		re int u,v,w;
		u=read(),v=read(),w=read();
		dis[u][v]=min(dis[u][v],w);
	}
	for(re int k=1 ; k<=n ; k++){
		for(re int i=1 ; i<=n ; i++){
			for(re int j=1 ; j<=n ; j++){
				dis[i][j]=min(dis[i][k]+dis[k][j],dis[i][j]);
			}
		}
	}
	re int ans=0;
	for(re int i=2 ; i<=n ; i++){
		ans+=dis[1][i]+dis[i][1];
	}
	printf("%d\n",ans);
	return 0;
}

(不要注意到我开了O2)