#include<bits/stdc++.h>
using namespace std;
long long m,n,a,b,c,tot;
const long long u=1000005;
long long head[u],ver[u],net[u],edge[u],st[u],dist[u],head2[u],dist2[u],ans;
typedef pair <long long,long long> PII;
priority_queue <PII,vector<PII>,greater<PII> > q;

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

void write(long long x)
{
    if(x<0){
    	putchar('-');
		x=-x;
	}
    if(x>9) 
		write(x/10);
    putchar(x%10+'0');
}

void add(long long a,long long b,long long c)
{
	net[++tot]=head[a];
	head[a]=tot;
	ver[tot]=b;
	edge[tot]=c;
}
void add2(long long a,long long b,long long c)
{
	net[++tot]=head2[a];
	head2[a]=tot;
	ver[tot]=b;
	edge[tot]=c;
}
void dijstla()
{
	memset(dist,0x3f,sizeof(dist));
	dist[1]=0;
	q.push({0,1});
	while(!q.empty())
	{
		PII temp=q.top();
		q.pop();
		long long dis=temp.first,v1=temp.second;
		if(st[v1]==1)
			continue;
		st[v1]=1;
		for(long long i=head[v1];i;i=net[i])
		{
			long long v=ver[i];
			if(dist[v]>dis+edge[i])
			{
				dist[v]=dis+edge[i];
				q.push({dist[v],v});
			}
		}
	}
	for(long long i=1;i<=n;++i)
		ans+=dist[i];
}
void dijstla2()
{
	memset(dist2,0x3f,sizeof(dist2));
	dist2[1]=0;
	q.push({0,1});
	while(!q.empty())
	{
		PII temp=q.top();
		q.pop();
		long long dis=temp.first,v1=temp.second;
		if(st[v1]==1)
			continue;
		st[v1]=1;
		for(long long i=head2[v1];i;i=net[i])
		{
			long long v=ver[i];
			if(dist2[v]>dis+edge[i])
			{
				dist2[v]=dis+edge[i];
				q.push({dist2[v],v});
			}
		}
	}
	for(long long i=1;i<=n;++i)
		ans+=dist2[i];
}


int main()
{
	n=read();
	m=read();
	for(long long i=1;i<=m;++i)
	{
		a=read();
		b=read();
		c=read();
		add(a,b,c);
		add2(b,a,c);
	}
	dijstla();
	memset(st,0,sizeof(st));
	dijstla2();
	write(ans);
	return 0;
}