#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
typedef long long ll;
const int maxn = 1e3 + 5;
const int maxm = 1e5 + 5;
int n, m;
ll ans;
ll dis[maxn<<1];
int head[maxn<<1], tot;
bool vis[maxn<<1];

struct edge {
	int to, w, nxt;
} e[maxm<<1];
void add(int u, int v, int w) {
	e[++tot].to = v;
	e[tot].w = w;
	e[tot].nxt = head[u];
	head[u] = tot;
}

struct node {
	int u, d;
	node(int _u = 0, int _d = 0) {
		u = _u, d = _d;
	}
	bool operator < (const node& x) const {
		return d > x.d;
	}
};

void dijkstra(int s) {
	priority_queue<node> q;
	q.push(node(s, 0));
	dis[s] = 0;
	memset(vis, 0, sizeof(vis));
	while(!q.empty()) {
		int u = q.top().u; q.pop();
		if(vis[u]) continue;
		vis[u] = true;
		for(int i = head[u]; i; i = e[i].nxt) {
			int v = e[i].to, w = e[i].w;
			if(dis[v] > dis[u] + w) {
				dis[v] = dis[u] + w;
				q.push(node(v, dis[v]));
			}
		}
	}
}

int main() {
//	freopen("test.in", "r", stdin);
	scanf("%d %d", &n, &m);
	for(int i = 1, a, b, c; i <= m; i++) {
		scanf("%d %d %d", &a, &b, &c);
		add(a, b, c);
		add(b+n, a+n, c);
	}
	memset(dis, 0x3f, sizeof(dis));
	dijkstra(1);
	for(int i = 2; i <= n; i++)
		ans += dis[i];
	dijkstra(1+n);
	for(int i = 2+n; i <= (n<<1); i++)
		ans += dis[i];
	printf("%lld\n", ans);
	return 0;
}