#include <bits/stdc++.h>
using namespace std;
long long n,m,i,j,be,Min,wyx,ans;
long long d[1000005],head[1000005],he[1000005];
struct Edge{
	long long next,to,dis;
}edge[1000005],ed[1000005];
int main()
{
	cin>>n>>m;
	for(i=1;i<=m;i++)
	{
		long long u,v,w,tot;
		scanf("%lld %lld %lld",&u,&v,&w);
		
		edge[++tot].next=head[u];
		edge[tot].to=v;
		edge[tot].dis=w;
		head[u]=tot;
		
		ed[tot].next=he[v];
		ed[tot].to=u;
		ed[tot].dis=w;
		he[v]=tot;
	}
	//出发 qwq 
	memset(d,0x3f,sizeof(d));
	d[1]=0; be=1;
	for(i=1;i<n;i++)
	{
		Min=0x3f3f3f3f;
		for(j=head[be];j;j=edge[j].next)
		{
			if(d[edge[j].to]>d[be]+edge[j].dis)
			{
				d[edge[j].to]=d[be]+edge[j].dis;
				if(d[edge[j].to]<Min)
				{
					Min=d[edge[j].to];
					wyx=edge[j].to;
				}
			}
		}
		be=wyx;
	}
	for(i=1;i<=n;i++)ans+=d[i];
	
	//回源点 qwq 
	memset(d,0x3f,sizeof(d));
	d[1]=0; be=1;
	for(i=1;i<n;i++)
	{
		Min=0x3f3f3f3f;
		for(j=he[be];j;j=ed[j].next)
		{
			if(d[ed[j].to]>d[be]+ed[j].dis)
			{
				d[ed[j].to]=d[be]+ed[j].dis;
				if(d[ed[j].to]<Min)
				{
					Min=d[ed[j].to];
					wyx=ed[j].to;
				}
			}
		}
		be=wyx;
	}
	for(i=1;i<=n;i++)ans+=d[i];
	
	printf("%lld",ans);
	return 0;
}

萌新刚学dijkstra，25分求调