#include<iostream>
#include<cstdio>
#include<cstring>
#define _ 0
using namespace std;
int n,m;
long long ans;
long long f[1005][1005]; 
int main (){
	std::ios::sync_with_stdio(false);
	cin>>n>>m;
	memset(f,0x3f,sizeof(f));
	for(int i=1;i<=m;i++){
		int x,y,z;
		cin>>x>>y>>z;
		f[x][y]=z;
	}
	for(int i=1;i<=n;i++)	f[i][i]=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][j]>f[i][k]+f[k][j])
					f[i][j]=f[i][k]+f[k][j];
			}
	for(int i=2;i<=n;i++){
		ans+=f[1][i]+f[i][1];
	} 
	cout<<ans;
	return 0^_^0;
}