#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>

using namespace std;
typedef pair<int, int>PII;
const int N = 1e3 + 10, M = 2e5 + 10;
const int INF = 0x3f3f3f3f;
int n, m;
int h[M], w[M], e[M], ne[M], idx;
int dist[N];
bool st[N];
int sum = 0;
void add(int a, int b, int c)
{
	e[idx] = b;
	w[idx] = c;
	ne[idx] = h[a];
	h[a] = idx++;
}
int dijkstra(int start, int end)
{
	memset(dist, INF, sizeof(dist));
	memset(st, false, sizeof(st));
	dist[start] = 0;
	priority_queue<PII, vector<PII>, greater<PII>>heap;
	heap.push({ 0, start });

	while (heap.size())
	{
		auto t = heap.top();
		heap.pop();

		int ver = t.second, distance = t.first;
		if (st[ver]) continue;
		st[ver] = true;

		for (int i = h[ver]; i != -1; i = ne[i])
		{
			int j = e[i];
			if (dist[j] > dist[ver] + w[i])
			{
				dist[j] = dist[ver] + w[i];
				heap.push({ dist[j], j });
			}
		}
	}
	if (dist[end] >= INF / 2) return -1;
	else return dist[end];
}
int main()
{
	memset(h, -1, sizeof(h));
	cin >> n >> m;
	for (int i = 1; i <= m; i++)
	{
		int a, b, w;
		cin >> a >> b >> w;
		add(a, b, w);
	}
	for (int i = 2; i <= n; i++)
	{
		sum += dijkstra(1, i) + dijkstra(i, 1);
	}
	cout << sum << endl;
	return 0;
}