#include<iostream>
#include<cstring>
using namespace std;
long long n,m,a[1005][1005],dis[1005],ans;
bool v[1005];
long long INF=2147483647;
void dijkstra()
{
	memset(v,false,sizeof(v));
    dis[1]=0;
	for(register int i=2;i<=n;++i) dis[i]=INF;
	for(register int i=1;i<=n;++i)
	{
		long long loc=1,minn=INF;
		for(register int j=1;j<=n;++j)
		{
			if(!v[j]&&dis[j]<=minn)
			{
				minn=dis[j];
				loc=j;
			}
		}
		v[loc]=true;
		for(register int j=1;j<=n;++j) 
		{
			if(a[loc][j]!=INF) dis[j]=min(dis[j],dis[loc]+a[loc][j]);
		}
	}
}
void tover()
{
	long long wa[1005][1005];
	memset(wa,INF,sizeof(wa));
	for(register int i=1;i<=n;++i)
	{
		for(register int j=1;j<=n;++j)
		{
			wa[i][j]=a[j][i];
		}
	}
	for(register int i=1;i<=n;++i)
	{
		for(register int j=1;j<=n;++j)
		{
			a[i][j]=wa[i][j];
		}
	}
}
int main()
{
	cin>>n>>m;
	for(register int i=1;i<=n;++i) for(register int j=1;j<=n;++j) a[i][j]=INF;
	for(register int i=1;i<=m;++i)
	{
		int u,v,w;
		cin>>u>>v>>w;
		a[u][v]=w;
	}
	dijkstra();
	for(register int i=2;i<=n;++i)
	{
		ans+=dis[i];
		dis[i]=0;
	}
//	cout<<ans;
	tover();
//	for(register int i=1;i<=n;++i)
//    {
//    	for(register int j=1;j<=n;++j)
//    	{
//    		cout<<a[i][j]<<" ";
//    	}
//    	cout<<endl;
//    }
	dijkstra();
//	for(register int i=1;i<=n;++i) cout<<dis[i]<<" ";
	for(register int i=2;i<=n;++i) ans+=dis[i];
	cout<<ans;
}