#include<bits/stdc++.h>
using namespace std;

const int inf=1e4+50;
int n,m,ans;

//邻接矩阵存图 
int f[1050][1050];

//floyd算法求最短路（非单源）
void floyd(){
	for(int k=1;k<=n;k++)
	for(int i=1;i<=n;i++)
	for(int j=1;j<=n;j++)
		f[i][j]=min(f[i][k]+f[k][j],f[i][j]);
} 
int main(){
	//读入第一行数据 
	cin>>n>>m;
	
	//初始化边长 
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			f[i][j]=inf; 
	for(int i=1;i<=n;i++)f[i][i]=0;
	
	//读入边长 
	for(int i=1;i<=m;i++){
	int u,v,w;
	cin>>u>>v>>w;
	f[u][v]=w;
	}
	
	floyd();
	
	//计算答案 
	for(int i=2;i<=n;i++){
		ans+=f[1][i]+f[i][1]; 
	}
	
	cout<<ans;
	return 0;
}