#include<bits/stdc++.h>
using namespace std;
struct node{
	int r,num;
};
int n,m;
bool operator<(node x,node y){
	if(x.num==y.num){
		return x.r>y.r;
	}
	else return x.num>y.num;
}
vector<node> g[1001];
vector<node> G[1001];
bool book[1001];
long long dist[1001];
void dij1(int s){
	memset(dist,0x3f,sizeof(dist));
	memset(book,0,sizeof(book));
	priority_queue<node> q;
	for(int i=0;i<g[s].size();i++){
		dist[g[s][i].r]=g[s][i].num;
		q.push(g[s][i]);
	}
	dist[s]=0;
	book[s]=true;
	int num=0;
	while(1){
		node a=q.top();q.pop();
		if(book[a.r]==true) continue;
		book[a.r]=true;
		num++;
		if(num==n-1) break;
		for(int i=0;i<g[a.r].size();i++){
			if(book[g[a.r][i].r]==true) continue;
			if(dist[g[a.r][i].r]>dist[a.r]+g[a.r][i].num){
				dist[g[a.r][i].r]=dist[a.r]+g[a.r][i].num;
			}
			q.push((node){g[a.r][i].r,dist[g[a.r][i].r]});
		}
	}
}
void dij2(int s){
	memset(dist,0x3f,sizeof(dist));
	memset(book,0,sizeof(book));
	priority_queue<node> q;
	for(int i=0;i<G[s].size();i++){
		dist[G[s][i].r]=G[s][i].num;
		q.push(G[s][i]);
	}
	dist[s]=0;
	book[s]=true;
	int num=0;
	while(1){
		node a=q.top();q.pop();
		if(book[a.r]==true) continue;
		book[a.r]=true;
		num++;
		if(num==n-1) break;
		for(int i=0;i<G[a.r].size();i++){
			if(book[G[a.r][i].r]==true) continue;
			if(dist[G[a.r][i].r]>dist[a.r]+G[a.r][i].num){
				dist[G[a.r][i].r]=dist[a.r]+G[a.r][i].num;
			}
			q.push((node){G[a.r][i].r,dist[G[a.r][i].r]});
		}
	}
}
int main(){
	long long ans=0;
	cin>>n>>m; 
	for(int i=1;i<=m;i++){
		int u,v,w;
		cin>>u>>v>>w;
		g[u].push_back((node){v,w}); 
		G[v].push_back((node){u,w});
	} 
	dij1(1);
	for(int i=1;i<=n;i++){
		ans+=dist[i];
	}
	dij2(1); 
	for(int i=1;i<=n;i++){
		ans+=dist[i];
	}
	cout<<ans;
}

WA on #2,不是重边，memset和爆int等问题