#include <fstream>
#include <vector>
#include <limits>
#include <algorithm>
#include <string.h>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
int t1,t2,sol[200000],i,j,n,k,tata[200001],x,y,z,S,nr;
struct df{
	int a;
	int b;
	int c;
}v[400001];
int cmp(df x,df y){
	return x.c<y.c;
}
int parinte(int nod){
	while(tata[nod]>0)
	   nod=tata[nod];
	return nod;
}
int main(){
	f>>n>>k;
   	for(i=1;i<=k;i++){
        f>>x>>y>>z;
		v[i].a=x;v[i].b=y;v[i].c=z;
    }
    sort(v+1,v+k+1,cmp);
 	for(i=1;i<=n;i++)
		tata[i]=-1;
	for(i=1;i<=k;i++){
		int t1=parinte(v[i].a);
		int t2=parinte(v[i].b);
		if(t1!=t2){
			if(tata[t1]<tata[t2]){
				tata[t1]+=tata[t2];
				tata[t2]=t1;

			}
			else{
				tata[t2]+=tata[t1];
				tata[t1]=t2;
			}
			nr++;
			S+=v[i].c;
			sol[nr]=i;
	
			if(nr==n-1)
				break;
				}

	}
	g<<S<<'\n'<<nr<<'\n';
	for(i=1;i<=nr;i++)
		g<<v[sol[i]].a<<' '<<v[sol[i]].b<<'\n';
    return 0;
}