#include <bits/stdc++.h>
#define INF 0x3f3f3f; 
using namespace std;
int n,m;
const int N=1e3+10,M=1e5+10;
//使用结构体存储图 
struct node{
	int ne,to,w;
}	e[M],fe[M];
int idx=1,fidx=1; 	//idx是边的索引 
int h[N],fh[N];
int vi[N],fvi[N];//用来标记某点是否被访问过 
int d[N],fd[N];

void add(int a,int b ,int c){
	e[idx].to=b;	//表示第 idx 条边通向 b 点
	e[idx].w=c;		//表示第 idx 条边的权值为 c
	e[idx].ne=h[a];	//表示以a为起点的第 idx 条边的下一条边为 h[a]（-1表示无边）
	h[a]=idx++;		//表示点 a 的上一条边为 idx
}

void fadd(int a,int b,int c){
	fe[fidx].to=b;
	fe[fidx].w=c;
	fe[fidx].ne=fh[a];
	fh[a]=fidx++;
}

void dij(int s)
{
	for(int i=1;i<=n;i++)	d[i]=INF;
	d[s]=0;
	
	for(int i=1;i<=n;i++)
	{
		int t=-1;
		for(int j=1;j<=n;j++)
			if(!vi[j] && (t==-1 || d[j]<d[t]) )
				t=j;
				
		vi[t]=1;
		for(int j=h[t]; j!=-1;j=e[j].ne )
		{
			int x=e[j].to;	
			int w=e[j].w;
			d[x]=min(d[x],d[t]+w);		
			//s到x的距离，小于经过t再加上j这条边权值的距离，更新d 
		}	
	}		
}

void fdij(int s)
{
	for(int i=1;i<=n;i++)	fd[i]=INF;
	fd[s]=0;
	
	for(int i=1;i<=n;i++)
	{
		int t=-1;
		for(int j=1;j<=n;j++)
			if(!fvi[j] && (t==-1 || fd[j]<fd[t]) )
				t=j;
				
		fvi[t]=1;
		for(int j=fh[t]; j!=-1;j=fe[j].ne)
		{
			int x=fe[j].to;		
			int w=fe[j].w;
			fd[x]=min(fd[x],fd[t]+w);		
		}	
	}		
}

int main(){
	memset(h,-1,sizeof h);
	memset(fh,-1,sizeof fh);
	
	cin>>n>>m;
	while(m--)
	{
		int u,v,w;
		cin>>u>>v>>w;
		add(u,v,w);
		fadd(v,u,w);
	}
	
	dij(1);
	fdij(1);
	int ans=0;
	for(int i=2;i<=n;i++)	ans += d[i]+fd[i];
	
	cout<<ans;
	return 0;
}