#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

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

typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
const int inf = 2e9;

int n, m, l, sum;
vii gf[200001];
priority_queue<ii, vii, greater<ii>> pq;
bool viz[200001];
int ch[200001], e[200001];

void prim(int s) {
	for (int i = 1; i <= n; i++)
		ch[i] = inf;
	ch[s] = 0;
	pq.push({ ch[s], s });
	while (!pq.empty()) {
		int vc = pq.top().first;
		int vn = pq.top().second;
		pq.pop();
		if (viz[vn])
			continue;
		viz[vn] = 1;
		sum += vc;
		for (ii i : gf[vn]) {
			int vvc = i.first;
			int vvn = i.second;
			if (!viz[vvn] && ch[vvn] > vvc) {
				ch[vvn] = vvc;
				e[vvn] = vn;
				pq.push({ ch[vvn], vvn });
			}
		}
	}
}

int main() {
	fin >> n >> m;
	for (int i = 1; i <= m; i++) {
		int x, y, c;
		fin >> x >> y >> c;
		gf[x].push_back({ c, y });
		gf[y].push_back({ c, x });
	}
	prim(1);
	fout << sum << "\n" << n - 1 << "\n";
    for (int i = 2; i <= n; i++)
        fout << e[i] << " " << i << "\n";
	return 0;
}