#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

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;
int p[200001], h[200001];

struct edge {
	int x, y, c;
}e[400001], print[400001];

int my_find(int x) {
	if (!p[x])
		return x;
	else {
		int tmp = my_find(p[x]);
		p[x] = tmp;
		return tmp;
	}
}

void my_union(int x, int y) {
	int rx = my_find(x), ry = my_find(y);
	if (rx != ry) {
		if (h[rx] > h[ry])
			p[ry] = rx;
		else {
			p[rx] = ry;
			if (h[rx] == h[ry])
				h[rx]++;
		}
	}
}

bool cmp(edge a, edge b) {
	return a.c < b.c;
}

void kruskal() {
	sort(e + 1, e + m + 1, cmp);
	int s = 0, l = 0;
	for (int i = 1; i <= m && l < n - 1; i++) {
		int rx = my_find(e[i].x), ry = my_find(e[i].y);
		if (rx != ry) {
			s += e[i].c;
			print[++l] = e[i];
			my_union(rx, ry);
		}
	}
	fout << s << "\n" << l << "\n";
	for (int i = 1; i <= l; i++)
		fout << print[i].x << " " << print[i].y << "\n";
}

int main() {
	fin >> n >> m;
	for (int i = 1; i <= m; i++)
		fin >> e[i].x >> e[i].y >> e[i].c;
	kruskal();
	return 0;
}