#include <bits/stdc++.h>

using namespace std;

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

int x[105],y[105],c[105],gr[105],ind[105];
vector <int> vans;

int grupa(int i){
	if(gr[i]==i)
		return i;
	gr[i]=grupa(gr[i]);
	return gr[i];
}

void reuniune(int i, int j){
	gr[grupa(i)]=grupa(j);
}

bool cmpf(int i, int j){
	return(c[i]<c[j]);
}

int main(){
	int n,m,i,j,ans=0;

	fin>>n>>m;

	for(i=1;i<=m;i++){
		fin>>x[i]>>y[i]>>c[i];
		ind[i]=i;
	}

	for(i=1;i<=n;i++)
		gr[i]=i;

	sort(ind+1,ind+m+1,cmpf);

	for(i=1;i<=m;i++){
		if(grupa(x[ind[i]])!=grupa(y[ind[i]])){
			ans+=c[ind[i]];
			reuniune(x[ind[i]],y[ind[i]]);
			vans.push_back(ind[i]);
		}
	}

	fout<<ans<<"\n"<<n-1<<"\n";
	for(i=0;i<n-1;i++)
		fout<<x[vans[i]]<<" "<<y[vans[i]]<<"\n";


	return 0;
}