#include<bits/stdc++.h>
using namespace std;
long long n,m,ans=0;
int f[1000][1000];
int main()
{
    cin>>n>>m; 
    for(int i=1;i<=n;i++)
    	for(int j=1;j<=n;j++) f[i][j]=2147483647;
    for(int i=1;i<=m;i++){
    	int u,v,w;
        cin>>u>>v>>w;
        f[u][v]=min(f[u][v],w);
    }
    for(int i=1;i<=n;i++)
    	for(int j=1;j<=n;j++)
			for(int k=1;k<=n;k++)
    		f[i][j]=min(f[i][k]+f[k][j],f[i][j]);
    for(int i=2;i<=n;i++) ans+=(f[1][i]+f[i][1]);
    cout<<ans;
    return 0;
}