#include<bits/stdc++.h>
using namespace std;
int n,m,ans=0;
struct node
{
	int to,value;
};
vector<node> maps[1145140];
int dis[1145140];
bool book[1145140];
queue<int> q;
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
    	int u;
    	node v;
    	scanf("%d%d%d",&u,&v.to,&v.value);
    	maps[u].push_back(v);
	}
	for(int i=2;i<=n;i++)
	{
		while(!q.empty()) q.pop();
		memset(dis,63,sizeof dis);
		memset(book,false,sizeof book);
		dis[1]=0,book[1]=true;
		q.push(1);
		while(!q.empty())
		{
			int u=q.front();
			book[u]=false;
			for(int j=0;j<maps[u].size();j++)
			{
				node v=maps[u][j];
				if(dis[v.to]>dis[u]+v.value)
				{
					dis[v.to]=dis[u]+v.value;
					if(book[v.to]==false)
					{
						book[v.to]=true;
						q.push(v.to);
				    }
				}
			}
			q.pop();
		}
		ans+=dis[i];
		while(!q.empty()) q.pop();
		memset(dis,63,sizeof dis);
		memset(book,false,sizeof book);
		dis[i]=0,book[i]=true;
		q.push(i);
		while(!q.empty())
		{
			int u=q.front();
			book[u]=false;
			for(int j=0;j<maps[u].size();j++)
			{
				node v=maps[u][j];
				if(dis[v.to]>dis[u]+v.value)
				{
					dis[v.to]=dis[u]+v.value;
					if(book[v.to]==false)
					{
						book[v.to]=true;
						q.push(v.to);
					}
				}
			}
			q.pop();
		}
		ans+=dis[1];
	}
	printf("%d\n",ans);
	return 0;
}