#include<bits/stdc++.h>
using namespace std;
int n,m,x,y,dis,head[2005],cnt=0,a[2005],c,d,e,ans=0;
pair<int,int> b;
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >p;
struct node
{
	int next,to,dis;
} edge[200005];
void add(int from,int to,int dis)
{
	edge[++cnt].next=head[from];
	edge[cnt].to=to;
	edge[cnt].dis=dis;
	head[from]=cnt;
}
int main()
{
	memset(a,-1,sizeof(a));
	cin>>n>>m;
	while (m--)
	{
		scanf("%d%d%d",&x,&y,&dis);
		add(x,y,dis);
		add(y+n,x+n,dis);
	}
	a[1]=a[1+n]=0;
	for (int i=head[1];i;i=edge[i].next)
	{
		d=edge[i].dis;
		e=edge[i].to;
		a[e]=d;
		p.push(make_pair(d,e));
	}
	for (int i=head[1+n];i;i=edge[i].next)
	{
		d=edge[i].dis;
		e=edge[i].to;
		a[e]=d;
		p.push(make_pair(d,e));
	}
	while (!p.empty())
	{
		b=p.top();
		p.pop();
		c=b.second;
		if (a[c]<b.first)
		continue;
		for (int i=head[c];i;i=edge[i].next)
		{
			d=edge[i].dis;
			e=edge[i].to;
			if (a[e]==-1 || a[c]+d<a[e])
			{
				a[e]=a[c]+d;
				p.push(make_pair(a[e],e));
			}
		}
	}
	for (int i=2;i<=n;++i)
	ans+=a[i]+a[i+n];
	cout<<ans;
}