#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF=1e10;
ll n,m,sum=0;
struct edge
{
	ll from,to,w;
	edge(ll a,ll b,ll c){from=a;to=b;w=c;}
};
vector <edge> e[100004];
struct s_node
{
	ll id,n_dis;
	s_node(ll a,ll b){id=a;n_dis=b;}
	bool operator < (const s_node & a)const
	{return n_dis>a.n_dis;}
};
ll dijkstra(int s)
{
	ll dis[100004];
	bool done[100004];
	for(int i=1;i<=n;i++)
	{
		dis[i]=INF;
		done[i]=false;
	}
	dis[s]=0;
	priority_queue <s_node> q;
	q.push(s_node(s,dis[s]));
	while(!q.empty())
	{
		if(s!=1&&done[1])break; 
		s_node u=q.top();
		q.pop();
		if(done[u.id])continue;
		done[u.id]=true;
		for(int i=0;i<e[u.id].size();i++)
		{
			edge y=e[u.id][i];
			if(done[y.to])continue;
			if(dis[y.to]>y.w+u.n_dis)
			{
				dis[y.to]=y.w+u.n_dis;
				q.push(s_node(y.to,dis[y.to]));
			}
		}
	}
	ll ans=0;
	if(s==1)for(int i=1;i<=n;i++)ans+=dis[i];
	else ans=dis[1];
	return ans;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>m;
	for(int i=0;i<m;i++)
	{
		ll aa,bb,cc;
		cin>>aa>>bb>>cc;
		e[aa].push_back(edge(aa,bb,cc));
	}
	for(int i=1;i<=n;i++)sum+=dijkstra(i);
	cout<<sum;
	return 0;
}