#include<bits/stdc++.h>
using namespace std;
const int N=2*1e6+5;
long long ans,dist[N],dist1[N],w[N],w1[N];
int a,b,c,idx,e[N],ne[N],h[N],e1[N],ne1[N],h1[N],v[N],n,m;

void dij1(){
	memset(dist,0x3f3f3f3f,sizeof dist);
	priority_queue<pair<long long,long long> > heap;
	dist[1]=0;
	heap.push(make_pair(0,1));
	while(!heap.empty()){
		long long x=heap.top().second;
		heap.pop();
		if(v[x]==1) continue;
		v[x]=1;
		for(int i=h[x];i!=-1;i=ne[i]){
			int j=e[i];
			if(dist[j]>dist[x]+w[i]) {
				dist[j]=dist[x]+w[i];
				heap.push(make_pair(dist[j],j));
			}
		}
	}
}
void dij2(){
	memset(v,0,sizeof v);
	memset(dist1,0x3f3f3f3f,sizeof dist1);
	priority_queue<pair<long long,long long> > heap;
	dist1[1]=0; 
	heap.push(make_pair(0,1));
	while(!heap.empty()){
		
		long long x=heap.top().second;
		heap.pop();
		if(v[x]==1) continue;
		v[x]=1;
		for(int i=h1[x];i!=-1;i=ne1[i]){
			int j=e1[i];
			if(dist1[j]>dist1[x]+w1[i]) {
				dist1[j]=dist1[x]+w1[i];
				heap.push(make_pair(dist[j],j));
			}
		}
	}
}

void add(int a,int b,int c){
	w[idx]=c;
	e[idx]=b;
	ne[idx]=h[a];
	h[a]=idx++;
	
}

void aad(int b,int a,int c){
	w1[idx]=c;
	e1[idx]=b;
	ne1[idx]=h1[a];
	h1[a]=idx++;
}


int main(){
	memset(h,-1,sizeof h);
	memset(h1,-1,sizeof h1);
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&a,&b,&c);
		add(a,b,c);
		aad(a,b,c);
	}
	dij1();
	idx=0;
	dij2();
	for(int i=2;i<=n;i++){
		ans+=dist[i];
		ans+=dist1[i];
	}
	cout<<ans;
	return 0;
}