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

using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
#define inf (1<<30);
#define nmax 200002

priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>> >q;
vector<pair<int, int>>g[nmax], rez;
int n, m, x, y, z, i, viz[nmax], s;

void prim() {
	pair<int, pair<int, int>> el;
	int i;
	for (auto& nod : g[1]) {
		q.push({ nod.first, {1, nod.second} });
	}
	viz[1] = 1;
	for (i = 1; i <= n - 1; i++) {
		while (1) {
			el = q.top();
			q.pop();
			if (viz[el.second.second] == 0) {
				break;
			}
		}
		s += el.first;
		viz[el.second.second] = 1;
		rez.push_back({ el.second.first, el.second.second });
		for (auto& nod : g[el.second.second]) {
			if (viz[nod.second] == 0) {
				q.push({ nod.first, {el.second.second, nod.second} });
			}
		}
	}
	fout << s << '\n' << n - 1 << '\n';
	for (auto& noduri : rez) {
		fout << noduri.first << ' ' << noduri.second << '\n';
	}
}

int main() {
	fin >> n >> m;
	for (i = 1; i <= m; i++) {
		fin >> x >> y >> z;
		g[x].push_back({ z,y });
		g[y].push_back({ z,x });
	}
	prim();
}