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

#define RANGE_MIN -1000
#define RANGE_MAX 1000

using namespace std;

int *E1, *E2, *EC, *Ei, *ES;

bool compara(int a, int b){
	return EC[a]<EC[b];
}

int gaseste(int *A, int i){
	if(A[i]==i)
		return i;
	return gaseste(A, A[i]);
}

inline void uneste(int *A, int *R, int x, int y){
	int xRoot=gaseste(A, x);
	int yRoot=gaseste(A, y);
	if(xRoot==yRoot)
		return;
	if(R[xRoot] < R[yRoot])
		A[xRoot]=yRoot;
	else if(R[xRoot] > R[yRoot])
		A[yRoot]=xRoot;
	else{
		A[yRoot]=xRoot;
		R[xRoot]++;
	}
}

int main(){
	int n, m, i, msel=0;
	long long sum=0;
	{//citire
		ifstream fp("apm.in");
		fp>>n>>m;
		E1=new int[m];
		E2=new int[m];
		EC=new int[m];
		Ei=new int[m];
		ES=new int[n-1];
		for(i=0; i<m; i++){
			fp>>E1[i]>>E2[i]>>EC[i];
			Ei[i]=i;
		}
		fp.close();
	}
	{//Kruskal
		int *A, *R;
		A=new int[n+1];
		R=new int[n+1];
		for(i=1; i<=n; i++){
			A[i]=i;
			R[i]=0;
		}
		sort(Ei, Ei+m, compara);
		for(i=0; i<m; i++)
			if(gaseste(A, E1[Ei[i]]) != gaseste(A, E2[Ei[i]])){
				ES[msel++]=Ei[i];
				sum+=EC[Ei[i]];
				if(msel==n-1)
					break;
				uneste(A, R, E1[Ei[i]], E2[Ei[i]]);
			}
		delete [] A;
		delete [] R;
	}
	{//afisare
		ofstream fp("apm.out");
		fp<<sum<<endl<<msel<<endl;
		for(i=0; i<msel; i++)
			fp<<E1[i]<<" "<<E2[i]<<endl;
	}
	return 0;
}