#include<bits/stdc++.h>
using namespace std;
vector <int> d[100500];
vector <int> e[100500];
long long dis[100500];
bool vis[100500];
int n,m;
priority_queue<pair<int,int> > q;
void dj(int s)
{
	int temp,y,z;
	memset(vis,0,sizeof(vis));
	memset(dis,0x3f,sizeof(dis));
	dis[s]=0;
	q.push(make_pair(0,s));
	while(!q.empty())
	{
		temp=q.top().second;
		q.pop();
		if(vis[temp]) continue;
		vis[temp]=1;
		for(int i=0;i<d[temp].size();i++)
		{
			y=d[temp][i]; z=e[temp][i];
			if(dis[y]>dis[temp]+z)
			{
				dis[y]=dis[temp]+z;
				q.push(make_pair(-dis[y],y));
			}
		} 
	}
}
int main() {
	int x,y,z,ans=0;
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		cin>>x>>y>>z;
		d[x].push_back(y);
		e[x].push_back(z);
	}
	dj(1);
	for(int i=1;i<=n;i++) ans+=dis[i];
	for(int i=2;i<=n;i++) 
	{
		dj(i);
		ans+=dis[1];
	}
	cout<<ans<<endl;
	return 0;
}