#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
#include<vector>
#define MAXN 1000010
using namespace std;

inline int read(){
	int x=0;int f=1;char ch=getchar();
	while(ch>'9'||ch<'0'){
		if(ch='-'){
			f=-f;
		}
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=x*10+ch-'0';
		ch=getchar();
	}
	return x*f;
}

typedef struct Edge{
	int w;
	int next;
	int to;
}E;

struct node{
	int dis;
	int pos;
	bool operator < (const node &x)const{
		return x.dis <dis ;
	}
};

E edge[MAXN];
const int INF=1e9+7;
int n;
int m;
int head[MAXN];
long long dis[MAXN];
bool visit[MAXN];
int cnt=0;
long long ans=0;

std::priority_queue<node> q;

void init(){
	memset(dis,INF,sizeof(dis));
	memset(visit,false,sizeof(visit));
}

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

void dijkstra(int x){
	init();
	dis[x]=0;
	q.push((node){0,x});
	while(!q.empty()){
		node tmp=q.top() ;
		q.pop() ;
		int value=tmp.dis ,posn=tmp.pos ;
		if(visit[posn]){
			continue;
		}
		visit[posn]=true;
		for(int i=head[posn];i!=-1;i=edge[i].next ){
			int t=edge[i].to ;
			if(dis[t]>edge[i].w +dis[posn]){
				dis[t]=edge[i].w +dis[posn];
				if(!visit[t]){
					q.push((node){dis[t],t}) ;
				}
			}
		}
	}  
}

int main(){
	memset(head,-1,sizeof(head));
	n=read();
	m=read();
	for(int i=1;i<=m;i++){
		int u,v,w;
		u=read();
		v=read();
		w=read();
		add(u,v,w);
		add(v+n,u+n,w);
	}
	dijkstra(1);
	for(int i=2;i<=n;i++){
		ans+=dis[i];
	}
	dijkstra(1+n);
	for(int i=2+n;i<=n<<1;i++){
		ans+=dis[i];
	}
	printf("%lld",ans);
	return 0;	
}