#include <bits/stdc++.h>

using namespace std;

const int N = 5005, M = 200005;
typedef pair<int, int> PII;

int cnt;
int n, m;
int x, y, z;
int head[N], ver[M], ed[M], ne[M];
int dis[N];
bool vis[N];
int ans;

void add (int x, int y, int z) {
	cnt ++;
	ver[cnt] = y;
	ed[cnt] = z;
	ne[cnt] = head[x];
	head[x] = cnt;
}

void dijkstra (int s) {
	priority_queue<int, vector<PII>, greater<PII> >q;
	q.push({0, s});
	dis[s] = 0;
	while (!q.empty()) {
		int x = q.top().first;
		int u = q.top().second;
		q.pop();
		if (vis[x]) continue;
		vis[x] = true;
		for (int i = head[u]; i != -1; i = ne[i]) {
			int v = ver[i];
			int e = ed[i];
			if (dis[v] > dis[u] + e) {
				dis[v] = dis[u] + e;
				q.push({dis[v], v});
			}
		}
	}
}


int main () {
    ios::sync_with_stdio(false);
	scanf("%d%d", &n, &m);
	memset(head, -1, sizeof(head));
	memset(dis, 0x7f, sizeof(dis));
	for (int i = 1; i <= m; i ++) {
		scanf("%d%d%d", &x, &y, &z);
		add(x, y, z);
	}
	dijkstra(1);
    for (int i = 2; i <= n; i ++) ans += dis[i];
    //memset(dis, 0x7f, sizeof(dis));
    //memset(vis, 0, sizeof(vis));
	for (int i = 2; i <= n; i ++) {
		memset(dis, 0x7f, sizeof(dis));
        memset(vis, 0, sizeof(vis));
        dijkstra(i);
		ans += dis[1];
	}
	printf("%d\n", ans);
	return 0;
}