#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m;
const int MAXN=10000006;


struct edge{
	int to;
	int dis;
	int next;
}e[MAXN],e_[MAXN];

int cnt,cnt_,head[MAXN],dis[MAXN],head_[MAXN];
bool vis[MAXN];

void addedge(int u,int v,int d)
{
	cnt++;
	e[cnt].dis=d;
	e[cnt].to=v;
	e[cnt].next=head[u];
	head[u]=cnt;
}

void addedge_(int u,int v,int d)
{
	cnt_++;
	e_[cnt_].dis=d;
	e_[cnt_].to=v;
	e_[cnt_].next=head_[u];
	head_[u]=cnt;
}

struct node{
	int dis;
	int pos;
	bool operator <(const node &x)const
	{
		x.dis<dis;
	}
};

priority_queue<node> q;

void dijsktra()
{
	dis[1]=0;
	q.push({0,1});
	while(!q.empty())
	{
		node tmp=q.top();
		q.pop();
		int x=tmp.pos,d=tmp.dis;
		if(vis[x])	continue;
		vis[x]=1;
		for(int i=head[x];i;i=e[i].next)
		{
			int y=e[i].to;
			if(dis[y]>dis[x]+e[i].dis)
			{
				dis[y]=dis[x]+e[i].dis;
				if(!vis[y])
				{
					q.push({dis[y],y});
				}
			}
		}
	}
}

void dijsktra_()
{
	dis[1]=0;
	q.push({0,1});
	while(!q.empty())
	{
		node tmp=q.top();
		q.pop();
		int x=tmp.pos,d=tmp.dis;
		if(vis[x])	continue;
		vis[x]=1;
		for(int i=head_[x];i;i=e_[i].next)
		{
			int y=e_[i].to;
			if(dis[y]>dis[x]+e_[i].dis)
			{
				dis[y]=dis[x]+e_[i].dis;
				if(!vis[y])
				{
					q.push({dis[y],y});
				}
			}
		}
	}
}

signed main()
{
	int ans=0;
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int u,v,d;
		cin>>u>>v>>d;
		addedge(u,v,d);
		addedge_(v,u,d);
	}
	for(int i=1;i<=n;i++)
	{
		dis[i]=0x7fffffff;
	}
	dijsktra();
	for(int i=1;i<=n;i++)
	{
//		cout<<dis[i]<<" ";
		ans+=dis[i];
	}
//	cout<<endl;
	
	memset(vis,0,sizeof(vis));
	for(int i=1;i<=n;i++)
	{
		dis[i]=0x7fffffff;
	}
	dijsktra_();
	for(int i=1;i<=n;i++)
	{
//		cout<<dis[i]<<" ";
		ans+=dis[i];
	}
//	cout<<endl;
	cout<<ans<<endl;
	return 0;
}