#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
FILE *in = fopen("apm.in", "r"), *out = fopen("apm.out", "w");

struct muchie{ int x, y, c;};
vector <muchie> graf, sol;
vector <int> tata, rang;
int n, m, mAlese, cost;

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

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

void Merge(muchie &M){
	int xRoot = Find(M.x), yRoot = Find(M.y);
	if (xRoot == yRoot) return;
	mAlese++; cost+= M.c; sol.push_back((muchie){M.x, M.y, M.c});
	
	(rang[xRoot] >= rang[yRoot]) ? tata[yRoot] = xRoot : tata[xRoot] = yRoot;
	if (rang[xRoot] == rang[yRoot]) rang[xRoot] ++;
}

int main(){
	int i, x, y, c;
	fscanf(in, "%d %d", &n, &m);
	
	for (i = 0; i < m; i++){
		fscanf(in, "%d %d %d", &x, &y, &c);
		graf.push_back((muchie){x, y, c});
	}
	for (i = 0; i <= n; i++) tata.push_back(i);
	rang.assign(n+1, 1);
	sort (graf.begin(), graf.end(), Compara);
	
	for (i = 0; i < m && mAlese < n-1; i++) Merge(graf[i]);
	
	fprintf(out, "%d\n%d\n", cost, sol.size());
	for (i = 0; i < n-1; i++) fprintf(out, "%d %d\n", sol[i].x, sol[i].y);
	return 0;
}