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

int n,m,u,v,w,dis[1000006],dis1[1000006];
bool vis[1000006];

struct edge{
	int u,v,w;
}e[1000006];int head[1000006],cnt;

struct edge1{
	int u,v,w;
}e1[1000006];int head1[1000006],cnt1;

void add(int u,int v,int w){
	e[++cnt].u=v;
	e[cnt].w=w;
	e[cnt].v=head[u];
	head[u]=cnt;
}

void add1(int u,int v,int w){
	e1[++cnt].u=v;
	e1[cnt].w=w;
	e1[cnt].v=head[u];
	head1[u]=cnt1;
}

struct node{
	int dis,id;
	bool operator<(const node &rhs)const{
		return rhs.dis<dis;
	}
};

void dijkstra(){
	priority_queue<node> q;
	dis[1]=0;
	q.push({0,1});
	while(!q.empty()){
		node tp=q.top();q.pop();
		int di=tp.dis;
		int u=tp.id;
		vis[u]=true;
		for(int i=head[u];i;i=e[i].v){
			int to=e[i].u,wei=e[i].w;
			if(!vis[to]&&dis[to]>dis[u]+wei){
				dis[to]=dis[u]+wei;
				q.push({dis[to],to});
			}
		}
	}
}

void dijkstra1(){
	priority_queue<node> q;
	dis1[1]=0;
	q.push({0,1});
	while(!q.empty()){
		node tp=q.top();q.pop();
		int di=tp.dis;
		int u=tp.id;
		vis[u]=false;
		for(int i=head[u];i;i=e[i].v){
			int to=e[i].u,wei=e[i].w;
			if(vis[to]&&dis1[to]>dis1[u]+wei){
				dis1[to]=dis1[u]+wei;
				q.push({dis1[to],to});
			}
		}
	}
}

int main(){
	cin>>n>>m;
	memset(dis,0x3f3f3f3f,sizeof dis);
	memset(dis1,0x3f3f3f3f,sizeof dis1);
	for(int i=1;i<=m;i++){
		cin>>u>>v>>w;
		add(u,v,w);
		add1(u,v,w);
	}
	memset(vis,false,sizeof vis);
	dijkstra();
	int ans=0;
	for(int i=1;i<=n;i++) ans+=dis[i];
	memset(vis,true,sizeof vis);
	dijkstra1();
	for(int i=1;i<=n;i++) ans+=dis1[i];
	cout<<ans<<endl;
	return 0;
}