#include<iostream>
#include<cstdio>
#include<algorithm> 
#include<cstdio>
#include<cmath>
using namespace std;
#define maxn 1000
#define INF  0x3ffff
long long g1[maxn][maxn],g2[maxn][maxn], d[maxn];
bool vis[maxn] = { false };//zhe ge dain shi fou bian li guo
long long n, m;
void dijkstra2(int s) {
	fill(vis + 1, vis + n + 1, false);
	fill(d, d + maxn, INF);
	d[s] = 0;
	for (int i = 0; i < n; i++) {
		int u = -1, min = INF;
		for (int j = 1; j <= n; j++) {
			if (d[j] < min&&vis[j] == false) {
				u = j;
				min = d[j];
			}
		}
		if (u == -1)
			return;
		vis[u] = true;
		for (int v = 1; v <= n; v++) {
			if (g2[u][v] + d[u] < d[v] && g2[u][v] != INF && vis[v] == false) {
				d[v] = g2[u][v] + d[u];
			}
		}
	}
}
void dijkstra1(int s) {
	fill(vis + 1, vis + n + 1, false);
	fill(d, d + maxn, INF);
	d[s] = 0;
	for (int i = 0; i < n; i++) {
		int u = -1, min = INF;
		for (int j = 1; j <= n; j++) {
			if (d[j] < min&&vis[j] == false) {
				u = j;
				min = d[j];
		    }
		}
		if (u == -1) 
			return;
		vis[u] = true;
		for (int v = 1; v <=n; v++) {
			if (g1[u][v] + d[u] < d[v] && g1[u][v] != INF&&vis[v]==false) {
				d[v] = g1[u][v] + d[u];
			}
		}
	}
}
int main() {
	cin >> n >> m;
	long long u, v,w;
	fill(g1[0], g1[0] + maxn * maxn, INF);
	fill(g2[0], g2[0] + maxn * maxn, INF);
	for (int i = 0; i < m; i++) {
		cin >> u >> v >> w;
		if (g1[u][v] != INF) {
			min(g1[u][v], w);
			min(g2[v][u], w);
		}
		else {
			g1[u][v] = w;
			g2[v][u] = w;
		}
	}
	dijkstra1(1);
	long long  sum = 0;
	for (int i = 1; i <= n; i++)
    sum += d[i];
	dijkstra2(1);
	for (int i = 1; i <= n; i++)
	sum += d[i];
	printf("%d", sum);
	return 0;
}