#include <fstream>
#include <queue>
#include <bitset>

using namespace std;

ifstream in ("apm.in");
ofstream out ("apm.out");

const int N = 200001;
const int M = 400001;
const int INF = 1e9;

vector<pair<int, int>> a[N];
priority_queue<pair<int, int>> pq;
int n, m, cost = 0;
int d[N], pred[N];
bitset<N> viz;

void input() {
	in >> n >> m;
	for (int i = 0; i < m; i++) {
		int x, y, c;
		in >> x >> y >> c;
		a[x].push_back({y, c});
		a[y].push_back({x, c});
	}
	in.close();
	return;
}

void apm() {
	pq.push({0, 1});
	for (int i = 2; i <= n; i++) {
		d[i] = INF;
	}
	while (!pq.empty()) {
		int x = pq.top().second;
		pq.pop();
		if (viz[x]) {
			continue;
		}
		cost += d[x];
		viz[x] = true;
		for (auto p : a[x]) {
			int y = p.first;
			int c = p.second;
			if (c < d[y] && !viz[y]) {
				pred[y] = x;
				d[y] = c;
				pq.push({-c, y});
			}
		}
	}
	return;
}

void output() {
	out << cost << "\n" << n - 1 << "\n";
	for (int i = 2; i <= n; i++) {
		out << i << " " << pred[i] << "\n";
	}
	out.close();
	return;
}

int main() {
	input();
	apm();
	output();
	return 0;
}