#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

struct L {
	long a, b, d;
};

long n, m, sumcrt;
long p[200001];
long size[200001];
vector<L> v, sol;

bool cmp(L a, L b) {
	if(a.d < b.d)
		return true;
	else if(a.d == b.d)
		if(a.a < b.a)
			return true;
		else if(a.a == b.a)
			return a.b < b.b;
		else return false;
	else return false;
}

long pf(long a) {
	while(a != p[a])
		a = p[a];
	return a;
}

bool un(long a, long b) {
	a = pf(a);
	b = pf(b);
	if(a == b)
		return false;
	if(size[a] > size[b]) {
		p[b] = a;
	} else if(size[a] == size[b]) {
		p[b] = a;
		size[a]++;
	} else {
		p[a] = b;
	}
	return true;
}

int main() {
	long i, j;
	L tmp;
	long a, b, d;
	freopen("apm.in", "r", stdin);
	freopen("apm.out", "w", stdout);
	scanf("%ld %ld", &n, &m);
	for(i = 1; i <= m; i++) {
		scanf("%ld %ld %ld", &a, &b, &d);
		tmp.a = a;
		tmp.b = b;
		tmp.d = d;
		v.push_back(tmp);
	}
	sort(v.begin(), v.end(), cmp);
	for(i = 1; i <= n; i++) {
		p[i] = i;
		size[i] = 1;
	}
	for(i = 0; i < m; i++)
		if(un(v[i].a, v[i].b)) {
			sumcrt += v[i].d;
			sol.push_back(v[i]);
			if(sol.size() == n - 1)
				break;
		}
	printf("%ld\n%ld\n", sumcrt, sol.size());
	for(i = 0; i < sol.size(); i++)
		printf("%ld %ld\n", sol[i].a, sol[i].b);
	return 0;
}