#include<bits/stdc++.h>
using namespace std;
const int N=1e6+86;
const int F=1911;
const int MAXS=1e9+86;
int n,m;
priority_queue<int> p;
int dis[N],dis1[N];
int a[F][F],ans,ba[F][F];
int l[F][F];
vector<int> b[N],bb[N];
int read(){
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=x*10+(c-'0');
		c=getchar();
	}
	return x*f;
}
void dijk(int k,vector<int> bx[],int disx[],int ax[][F]){
	disx[k]=0;
	p.push(k);
	while(!p.empty()){
		int now=p.top();
		p.pop();
		for(int i=0;i<bx[now].size();i++){
			if(disx[now]+ax[now][bx[now][i]]<=disx[bx[now][i]]){
				p.push(bx[now][i]);
				disx[bx[now][i]]=disx[now]+ax[now][bx[now][i]];
			}
		}
	}
	return;
}
int x,y,z;
int main(){
	n=read();m=read();
	for(int i=1;i<=m;i++){
		x=read();y=read();z=read();
		if(l[x][y]==0){
			l[x][y]=1;
			a[x][y]=z;//邻接矩阵方便取边权 
			ba[y][x]=z;
			b[x].push_back(y);//邻接表 
			bb[y].push_back(x);//反向建图 
		}else{//处理重边 
			a[x][y]=min(a[x][y],z);
			ba[y][x]=min(ba[y][x],z);
		}
	}
	for(int i=1;i<=n;i++){
		dis[i]=MAXS;
		dis1[i]=MAXS;
	}
	dijk(1,b,dis,a);//正向dijkstra 
	dijk(1,bb,dis1,ba);//反向dijkstra 
	for(int i=1;i<=n;i++){
		ans+=dis[i]+dis1[i];
	}
	cout<<ans;
	return 0;
}