#include <iostream>
#include <cstdio>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <cmath>
#include <fstream>
using namespace std;
#define inf 0xfffffff
#define MOD 1999999973

int n, m, rad[200010], sol;
struct muchie{
	int a, b, c;
} u[400010];
bool viz[400010];

int tata(int x) {
	if (x == rad[x]) return x; {
		rad[x] = tata(rad[x]);
		return rad[x];
	}
}

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

int main() {
	int op, x, y;
	
	freopen("apm.in","r",stdin);
	freopen("apm.out","w",stdout);

	scanf("%d %d", &n, &m);
	for (int i = 1; i <= n; i++) rad[i] = i;
	for (int i = 1; i <= m; i++) {
		scanf("%d %d %d", &u[i].a, &u[i].b, &u[i].c);
	}

	sort(u+1, u+m+1, cmp);
	
	int p = 1;
	for (int i = 1; i < n; i++) {
		while (tata(u[p].a) == tata(u[p].b)) p++;
		sol += u[p].c;
		viz[p] = 1;	
		rad[tata(u[p].a)] = tata(u[p].b);
	}
	
	printf("%d\n", sol);
	printf("%d\n", n-1);
	for (int i = 1; i <= m; i++)
		if (viz[i]) printf("%d %d\n", u[i].a, u[i].b);
	
	return 0;
}