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

struct muchie{
		int i,f,cost;
		friend bool operator <(const muchie a, const muchie b){ return a.cost<b.cost; }
	};
vector<muchie> v;
int tata[200010],n,m, ok[200010],level[200010];

int radacina(int x){
	int y=x,tmp;
	while(tata[x])
		x = tata[x];
	while(y-x)
		tmp=tata[y], tata[y] = x, y=tmp;
	return x;
}

int main(){
	ifstream fin("apm.in");
	ofstream fout("apm.out");
	fin>>n>>m;
	v.reserve(m+5);
	muchie mc;
	for(int i =0;i<m;i++){
		fin>>mc.i>>mc.f>>mc.cost;
		v.push_back(mc);
	}
	sort(v.begin(), v.end());
	int ri,rf,nrm=0,cost=0;
	for(int i=0;i<m && nrm<m-1;++i)
	{
		ri=radacina(v[i].i);
		rf=radacina(v[i].f);
		if(ri!=rf)
		{
			ok[++nrm] = i;
			if(level[ri]<level[rf])
				tata[rf] = ri;
			else
				if(level[ri]>level[rf])
					tata[ri] = rf;
				else
					tata[ri] = rf, level[ri]++;
			
			cost+=v[i].cost;
			
		}
		
	}
	fout<<cost<<endl<<nrm<<endl;
	for(int i=1;i<=nrm;i++)
			fout<<v[ok[i]].i<<" "<<v[ok[i]].f<<endl;
	return 0;		
}