#include<bits/stdc++.h>
#define endl '\n'
//#define int long long
using namespace std;
template<typename T> void read(T&x){
	int sign=1;x=0;char c;
	do{
		c=getchar();
		if(c=='-') sign=-1;
	}while(!isdigit(c));
	do{
		x=x*10+c-'0';
		c=getchar();
	}while(isdigit(c));
	x*=sign;
}
struct node{
	long long hao,shu;
	friend bool operator < (node a,node b){
		return a.shu>b.shu;
	}
};
priority_queue<node> q1;
priority_queue<node> q2;
long long ans;
int n,m;
struct op1{
	int to,next,shu;
}f1[1000010];
struct op2{
	int to,next,shu;
}f2[1000010];
int dis1[1000010];
int dis2[1000010];
long long d[1000010];
bool ff[1000010];
int k1,k2;
int u,v,w;
void add1(int u,int v,int w){
	k1++;
	f1[k1].to=v;
	f1[k1].shu=w;
	f1[k1].next=dis1[u];
	dis1[u]=k1;
}
void add2(int u,int v,int w){
	k2++;
	f2[k2].to=v;
	f2[k2].shu=w;
	f2[k2].next=dis2[u];
	dis2[u]=k2;
}
signed main(){
	read(n),read(m);
	memset(dis1,-1,sizeof(dis1));
	memset(dis2,-1,sizeof(dis2));
	for(int i=1;i<=m;i++){
		read(u),read(v),read(w);
		add1(u,v,w);
		add2(v,u,w);
	}
	memset(d,0x3f3f3f3f,sizeof(d));
//	memset(ff,0,sizeof(ff));
	d[1]=0;
	q1.push({1,d[1]});
	for(int k=1;k<=n;k++){
		node e=q1.top();
		q1.pop();
		int uu=e.hao;
		ff[uu]=1;
		for(int i=dis1[uu];i!=-1;i=f1[i].next){
			int vv=f1[i].to;
			int ss=f1[i].shu;
			if(d[uu]+ss<d[vv]&&ff[vv]==0){
				d[vv]=d[uu]+ss;
				q1.push({vv,d[vv]});
			}
		}
	}
//	for(int i=1;i<=n;i++){
//		cout<<d[i]<<" ";
//	}
//	cout<<endl;
	for(int i=1;i<=n;i++){
		ans+=d[i];
	}
	memset(d,0x3f3f3f3f,sizeof(d));
	memset(ff,0,sizeof(ff));
	
	d[1]=0;
	q2.push({1,d[1]});
	for(int k=1;k<=n;k++){
		node e=q2.top();
		q2.pop();
		int uu=e.hao;
		ff[uu]=1;
		for(int i=dis2[uu];i!=-1;i=f2[i].next){
			int vv=f2[i].to;
			int ss=f2[i].shu;
			if(d[uu]+ss<d[vv]&&ff[vv]==0){
				d[vv]=d[uu]+ss;
				q2.push({vv,d[vv]});
			}
		}
	}
	for(int i=1;i<=n;i++){
		ans+=d[i];
	}
//	for(int i=1;i<=n;i++){
//		cout<<d[i]<<" ";
//	}
//	cout<<endl;
	cout<<(long long)ans;
	return 0;
}