#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <string.h>
using namespace std;
#define INF 0x3f3f3f3f
const int maxn = 1e5+1;
int n, m;
int pre[maxn];
int disk[maxn];
struct way
{
	vector<int> v;
	vector<int> w;
};
vector<way> solid;
int sum = 0, middle = INF;
void dijkstra(int x,int y)
{
	queue<pair<int, int>> q;//pos + w;
	memset(pre, 0, maxn);
	memset(disk, INF, maxn);
	q.push(make_pair(x, 0));
	disk[x] = 0;
	while (!q.empty())
	{
		int u = q.front().first;
		pre[u] = 0;
		q.pop();
		if (disk[u] == INF||u==y)
		{
			continue;
		}
		for (int i = 0; i < solid[u].v.size(); i++)
		{
			int v = solid[u].v[i], wx = solid[u].w[i];
			if (disk[v] > disk[u] + wx)
			{
				disk[v] = disk[u] + wx;
				if (pre[v] == 0)
				{
					pre[v] = -1;
					q.push(make_pair(v, disk[v]));
				}
			}
		}
	}
}
int main()
{
	cin >> n >> m;
	solid.resize(m + 1);
	for (int i = 0; i < m; i++)
	{
		int u, v, w; cin >> u >> v >> w;
		solid[v].v.push_back(u), solid[v].w.push_back(w);
		//solid[u].v.push_back(v), solid[u].w.push_back(w);
	}
	dijkstra(1,-1);
	for (int i = 2; i <= n; i++)
	{
		sum += disk[i];
	}
	for (int i = 2; i <= n; i++)
	{
		dijkstra(i,1);
		sum += disk[1];
	}
	cout << sum;
}