#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#define nmax 400100
using namespace std;

vector <int> vsol;
int x[nmax],y[nmax],c[nmax],gr[nmax],ind[nmax];
int n,m;

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

void uni(int i,int j){
	gr[anc(i)]=anc(j);
}

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

int main(){
	int sol=0;
	ifstream fin("apm.in");
	fin>>n>>m;
	for(int i=1;i<=m;++i)
	{
		fin>>x[i]>>y[i]>>c[i];
		ind[i]=i;
	}
	for(int i=1; i<=n;++i) gr[i]=i;
	sort(ind+1,ind+m+1,cmpf);
	for(int i=1;i<=m;++i)
		if(anc(x[ind[i]]) != anc(y[ind[i]])){
		sol += c[ind[i]];
		uni(x[ind[i]],y[ind[i]]);
		vsol.push_back(ind[i]);
	}
	ofstream fout("apm.out");
	fout<<sol<<'\n';
	fout<<n-1<<'\n';
	for(int i=0;i<n-1;i++)
		fout<<x[vsol[i]]<<' '<<y[vsol[i]]<<'\n';
	fout.close();
	fin.close();
return 0;
}