#include<iostream>
#include<algorithm>
using namespace std;
const int N=510;
int dist[N][N];
int n,m;

void floyd()
{
	for(int k=1;k<=n;k++)
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
			dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);
	
}
int main()
{
	cin>>n>>m;
	
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
		{
			if(i==j)
			dist[i][j]=0;
			else
			dist[i][j]=0x3f3f3f;
		}	
	
	for(int i=0;i<m;i++)
	{
		int u,v,w;
		cin>>u>>v>>w;
		dist[u][v] = min(dist[v][u], w);
	} 
	floyd();
	int ans=0;
	for(int i=2;i<=n;i++)
	ans=ans+dist[1][i]+dist[i][1];
	
	cout<<ans;
}