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

#define N 200000

using namespace std;

int E1[2*N], E2[2*N], EC[2*N], Ei[2*N], ES[N], NP[N+1];

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

int gaseste(int i){
	int rad=i, x=i;
	while(rad!=NP[rad])
		rad=NP[rad];
	while(x!=NP[x]){
		int z=NP[x];
		NP[x]=rad;
		x=z;
	}
	return rad;
}

inline void uneste(int x, int y){
	NP[gaseste(x)]=gaseste(y);
}

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