rt，WA 25.

#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 5;

struct Edge {
	int to, val, nxt;
} e[N], E[N];
struct Node {
	int to, val;
	Node(int _to, int _val) : to(_to), val(_val) {}
	bool operator < (const Node &oth) const {
		return val > oth.val;
	}
};

int n, m;
int head[N], Head[N], cnt, Cnt;
int dis[N], Dis[N];
bool in[N], In[N];
long long sum;

void Add(int u, int v, int w) {
	e[++cnt].to = v;
	e[cnt].nxt = head[u];
	e[cnt].val = w;
	head[u] = cnt;
	E[++Cnt].to = u;
	E[Cnt].nxt = Head[v];
	E[Cnt].val = w;
	Head[v] = Cnt;
}

void dijkstra() {
	memset(dis, 0x3f, sizeof dis);
	dis[1] = 0;
	memset(in, false, sizeof in);
	priority_queue<Node> q;
	q.push(Node(1, 0));
	while(!q.empty()) {
		Node u = q.top();
		q.pop();
		in[u.to] = false;
		for(int i = head[u.to]; i; i = e[i].nxt) {
			int v = e[i].to, w = e[i].val;
			if(u.val + w < dis[v]) {
				dis[v] = u.val + w;
				if(!in[v]) {
					in[v] = true;
					q.push(Node(v, dis[v]));
				}
			}
		}
	} 
}

void Dijkstra() {
	memset(Dis, 0x3f, sizeof Dis);
	Dis[1] = 0;
	memset(In, false, sizeof In);
	priority_queue<Node> q;
	q.push(Node(1, 0));
	while(!q.empty()) {
		Node u = q.top();
		q.pop();
		In[u.to] = false;
		for(int i = Head[u.to]; i; i = E[i].nxt) {
			int v = E[i].to, w = E[i].val;
			if(u.val + w < Dis[v]) {
				Dis[v] = u.val + w;
				if(!In[v]) {
					In[v] = true;
					q.push(Node(v, Dis[v]));
				}
			}
		}
	} 
}

int main() {
	cin >> n >> m;
	for(int i = 1; i <= m; i++) {
		int u, v, w;
		scanf("%d%d%d", &u, &v, &w);
		Add(u, v, w);
	}
	dijkstra();
	Dijkstra();
	for(int i = 2; i <= n; i++) sum += dis[i] + Dis[i];
	cout << sum << endl;
	return 0;
}