#include<bits/stdc++.h>
using namespace std;
struct node{
	long long x,w;
	node(long long  _x=0,long long _w=0):x(_x),w(_w){}
	bool operator <(const node&a)const{return w>a.w;}
};
long long n,m,dis[1000001],ans=0;
bool v[1000001];
vector<node>T1[1000010],T2[1000001];
priority_queue<node>que;
int main()
{
	std::ios::sync_with_stdio(false);
	cin>>n>>m;
	memset(dis,0x3f,sizeof(dis));
	//for(int i=1;i<=n;i++)cout<<dis[i]<<" ";//
	//cout<<endl;//
	int x,y,z;
	for(int i=1;i<=m;i++)
	{
		cin>>x>>y>>z;
		if(x==y)continue;
		T1[x].push_back(node(y,z));
		T2[y].push_back(node(x,z));
	}
	dis[1]=0;
	que.push(node(1,0));
	while(!que.empty())
	{
		x=que.top().x;
		que.pop();
		if(v[x])continue;
		v[x]=1;
		que.pop();
		for(int i=0;i<T1[x].size();i++)
		{
			if(v[T1[x][i].x]==0&&dis[T1[x][i].x]>T1[x][i].w+dis[x])
			{
				dis[T1[x][i].x]=T1[x][i].w+dis[x];
				que.push(node(T1[x][i].x,dis[T1[x][i].x]));
			}
		}
	}
//	for(int i=1;i<=n;i++)cout<<dis[i]<<" ";//
//	cout<<endl;//
	for(int i=2;i<=n;i++)ans+=dis[i];
//	cout<<ans<<endl;
	for(int i=2;i<=n;i++)
	{
		memset(dis,0x3f,sizeof(dis));
		memset(v,0,sizeof(v));
		que.push(node(i,0));
		dis[i]=0;
		while(!que.empty())
		{
			x=que.top().x;
			que.pop();
			if(v[x])continue;
			v[x]=1;
			que.pop();
			for(int i=0;i<T2[x].size();i++)
			{
				if(v[T2[x][i].x]==0&&dis[T2[x][i].x]>T2[x][i].w+dis[x])
				{
					dis[T2[x][i].x]=T2[x][i].w+dis[x];
					que.push(node(T2[x][i].x,dis[T2[x][i].x]));
				}
			}
			if(x==1)break;
		}
		ans+=dis[1];
	}
	cout<<ans*2;
	return 0;
 }