#include<bits/stdc++.h>
using namespace std;
int n,m,ans;
int dis[1005],fdis[1005];
struct EDGE{
	int to,len;
};
vector<EDGE>edge[1005];
vector<EDGE>fedge[1005];
bool has[1005];
bool fhas[1005];
void dijkstra(){
	priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >pq;
	pq.push(make_pair(0,1));
	dis[1]=0;
	while(!pq.empty()){		
		int id=pq.top().second;
		pq.pop();
		if(has[id]) continue;
		has[id]=true;
		for(int i=0;i<edge[id].size();i++){
			int to=edge[id][i].to;
			if(!has[to]&&dis[to]>dis[id]+edge[id][i].to){
				dis[to]=dis[id]+edge[id][i].to;
				pq.push(make_pair(dis[to],to));
			}
		}
	}
}
void fdijkstra(){
	priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >pq;
	pq.push(make_pair(0,1));
	fdis[1]=0;
	while(!pq.empty()){		
		int id=pq.top().second;
		pq.pop();
		if(fhas[id]) continue;
		fhas[id]=true;
		for(int i=0;i<fedge[id].size();i++){
			int to=fedge[id][i].to;
			if(!fhas[to]&&fdis[to]>fdis[id]+fedge[id][i].to){
				fdis[to]=fdis[id]+fedge[id][i].to;
				pq.push(make_pair(fdis[to],to));
			}
		}
	}
}
int main(){
	memset(dis,0x3f,sizeof(dis));
	memset(fdis,0x3f,sizeof(fdis));
	cin>>n>>m;
	int ui,vi,wi;
	for(int i=1;i<=m;i++){
		cin>>ui>>vi>>wi;
		edge[ui].push_back({vi,wi});
		fedge[vi].push_back({ui,wi});
	}	
	dijkstra();
	fdijkstra();
	for(int i=1;i<=n;i++){
		ans=ans+dis[i]+fdis[i];
	}
	cout<<ans;
	return 0;
}