#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int inf=100001;
int u,v,w,ans,dis[1001],f[1001][1001],n,m;
bool book[100001];
queue<int> q;
void dijkstra(){
	int x,i,k,ans,sum;
	while(!q.empty()){
		x=q.front();
		sum=-1;
		book[x]=true;
		ans=inf;
		for(i=1;i<=n;i++){
		   if(f[x][i]!=inf&&book[i]==false){
		   dis[i]=min(dis[i],dis[x]+f[x][i]);
		   if(ans>dis[i]){
		   	ans=dis[i];
		   	sum=i;
		   }
	       }
		}
		if(sum!=-1)
		q.push(sum);
		q.pop(); 
	}
}
void over(){
	int i,j;
    for(i=1;i<=n;i++){
        for(j=i+1;j<=n;j++){
            swap(f[i][j],f[j][i]);
        }
    }
}
int main(){
	int i,j,k,ans=0;
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++)
	for(j=1;j<=n;j++)
	if(i!=j)
	f[i][j]=inf;
	for(i=1;i<=m;i++){
		scanf("%d%d%d",&u,&v,&w);
		f[u][v]=min(f[u][v],w);
	}
    dis[1]=0;
    for(i=2;i<=n;i++) dis[i]=f[1][i];
    q.push(1);
    dijkstra();
    for(i=2;i<=n;i++)
	ans+=dis[i];
    over();
    for(i=2;i<=m;i++) book[i]=false;
    for(i=2;i<=n;i++) dis[i]=f[1][i];
    q.push(1);
    dijkstra();
    for(i=2;i<=n;i++)
	ans+=dis[i];
	printf("%d",ans);
	return 0;
}