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

using namespace std;

struct nodp{
	int r;
	nodp *p;
};

struct muchie{
	int c1, c2, cost;
	bool sel;
	bool operator<(muchie const & b){
		return cost<b.cost;
	}
};

void cset(nodp * x){
	x->p=x;
	x->r=0;
}

nodp * gaseste(nodp * x){
	if(x->p==x)
		return x->p;
	return gaseste(x->p);
}

inline void uneste(nodp * x, nodp * y){
	nodp * xRoot=gaseste(x);
	nodp * yRoot=gaseste(y);
	if(xRoot==yRoot)
		return;
	if(xRoot->r < yRoot->r)
		xRoot->p=yRoot;
	else if(xRoot->r > yRoot->r)
		yRoot->p=xRoot;
	else{
		yRoot->p=xRoot;
		xRoot->r++;
	}
}

int main(){
	int n, m, i, sum=0, msel=0;
	muchie *M;
	{//citire
		ifstream fp("apm.in");
		fp>>n>>m;
		M=new muchie[m];
		for(i=0; i<m; i++){
			fp>>M[i].c1>>M[i].c2>>M[i].cost;
			M[i].sel=0;
		}
		fp.close();
	}
	{//Kruskal
		nodp *N;
		N=new nodp[n+1];
		for(i=1; i<=n; i++)
			cset(&N[i]);
		sort(M, M+m);
		for(i=0; i<m; i++)
			if(gaseste(&N[M[i].c1]) != gaseste(&N[M[i].c2])){
				M[i].sel=1;
				sum+=M[i].cost;
				msel++;
				if(msel==n-1)
					break;
				uneste(&N[M[i].c1], &N[M[i].c2]);
			}
	}
	{//afisare
		ofstream fp("apm.out");
		fp<<sum<<endl<<msel<<endl;
		for(i=0; i<m; i++)
			if(M[i].sel)
				fp<<M[i].c1<<" "<<M[i].c2<<endl;
	}
	return 0;
}