#include <fstream>
#include <algorithm>
using namespace std; 

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

struct muchie{
	int x, y, c;
} G[200001], A[200001];

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

int main(){
	int n, m, t[200001], S = 0, cnt = 0;
	fin >> n >> m;
	for(int i = 1; i <= m; i ++)
		fin >> G[i].x >> G[i].y >> G[i].c;
	sort(G + 1, G + m + 1, compara);
	for(int i = 1; i <= n; i ++)
		t[i] = i;
	for(int i = 1; cnt < n - 1; i ++)
		if(t[G[i].x] != t[G[i].y]){
			S += G[i].c;
			A[++ cnt] = G[i];
			int x = t[G[i].x], y = t[G[i].y];
			for(int j = 1; j <= n; j ++)
				if(t[j] == y)
					t[j] = x;
		}
	fout << S << "\n" << cnt << "\n";
	for(int i = 1; i < n; i ++)
		fout << A[i].x << " " << A[i].y << "\n";
}