#include <bits/stdc++.h>
using namespace std;
struct node {int u,v;};
#define maxn 1000+10
vector <node> g[maxn];
vector <node> gg[maxn];
int f[maxn]={0};
bool operator < (const node& a,const node& b){
	return a.v>b.v;
}
void d(int x,int sum){
	bool vis[maxn]={0};
	priority_queue<node> q;
	q.push( (node){x,0} );
	while(q.size()!=0){
		node t=q.top(); q.pop();
		int u=t.u;
		
		if(vis[u]) continue;
		else vis[u]=1;
		if(sum==1){
			for(int i=0;i<g[u].size();i++){
				node to=g[u][i];
				
				if(f[to.u] > f[u]+to.v){
					f[to.u] = f[u]+to.v;
					q.push( (node){to.u,f[to.u]} );
				}
			}
		}else{
			for(int i=0;i<gg[u].size();i++){
				node to=gg[u][i];
				
				if(f[to.u] > f[u]+to.v){
					f[to.u] = f[u]+to.v;
					q.push( (node){to.u,f[to.u]} );
				}
			}
		}
		
	}
		
}
int main(){
	int n,m;
	scanf("%d%d",&n,&m);
	
	for(int i=0;i<m;i++){
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		g[x].push_back( (node){y,z} );
		gg[y].push_back( (node){x,z} );
	}
	int ans=0;
	
	
	memset(f,0x3f3f,sizeof(f));
	d(1,1);
	for(int i=2;i<=n;i++) ans+=f[i];
	
	memset(f,0x3f3f,sizeof(f));
	d(1,2);
	for(int i=2;i<=n;i++) ans+=f[i];
	
	printf("%d",ans);
	return 0;
}

样例都过不了 qwq