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

#define endl '\n'

const long long INF = 1e18;

const int MAX_NODE_SIZE = 1e6;
const int MAX_EDGE_SIZE = 1e6;

struct edge_point {

	int value, to, next;
} edge_vector[MAX_EDGE_SIZE << 1];

struct _queue_node {

	long long dislance;

	int _ID;

	_queue_node (long long DISLANCE, int ID) : dislance (DISLANCE), _ID (ID) {}

	bool operator > (const _queue_node cmp) const {

		return dislance > cmp.dislance;
	}
};

std :: priority_queue <_queue_node, std :: vector <_queue_node>, std :: greater <_queue_node> > _queue;

long long _dislance[MAX_NODE_SIZE << 1];

int head[MAX_NODE_SIZE << 1];

int count_Edge;

void add_edge (int st, int ed, int dislance) {

	++ count_Edge;

	edge_vector[count_Edge].to = ed;
	edge_vector[count_Edge].next = head[st];
	edge_vector[count_Edge].value = dislance;

	head[st] = count_Edge;

	return ;
}

void dijkstra (int _start_node) {

	_dislance[_start_node] = 0;

	_queue.push (_queue_node (0, _start_node));

	while (not _queue.empty ()) {

		_queue_node _this_node = _queue.top ();

		_queue.pop ();

		if (_dislance[_this_node._ID] < _this_node.dislance) {

			continue;
		}

		for (int i = head[_this_node._ID]; ~ i; i = edge_vector[i].next) {

			const int To_node = edge_vector[i].to;

			if (_dislance[To_node] > _dislance[_this_node._ID] + edge_vector[i].value) {

				_dislance[To_node] = _dislance[_this_node._ID] + edge_vector[i].value;

				_queue.push (_queue_node (_dislance[To_node], To_node));
			}
		}
	}

	return ;
}

int N, M, answer;

int main (void) {

	std :: ios :: sync_with_stdio (false);
	std :: cin.tie (nullptr);
	std :: cout.tie (nullptr);

	std :: cin >> N >> M;

	for (int i = 0; i < (N << 1); ++ i) {

		head[i] = -1;
	}

	for (int i = 0; i < M; ++ i) {

		int st, ed, value;

		std :: cin >> st >> ed >> value;

		add_edge (st, ed, value);
		add_edge (ed + N, st + N, value);
	}

	for (int i = 0; i < (N << 1); ++ i) {

		_dislance[i] = INF;
	}

	dijkstra (0);

	answer = 0;

	for (int i = 1; i < N; ++ i) {

		answer += _dislance[i];
	}

	dijkstra (N + 1);

	for (int i = N + 1; i < (N << 1); ++ i) {

		answer += _dislance[i];
	}

	std :: cout << answer << endl;

	return 0;
}

看着应该没错啊？（自我感觉良好）