#include<fstream>
#include<algorithm>
using namespace std;
ifstream fi("apm.in");
ofstream fo("apm.out");

struct muchie{
	int x;
	int y;
	int cost;
};

const int MAX_N = 200005;
const int MAX_M = 400005;

int tata[MAX_N],rang[MAX_N];
muchie e[MAX_M];
int i,n,m;
int sol,solm[MAX_N],nr_m;

bool comp(muchie a, muchie b){
	 return (a.cost<=b.cost);
}

int radacina(int x){
	while(tata[x]!=x) x=tata[x];
	return x;
}

void uneste(int x, int y){
	 if(rang[x]>rang[y]) tata[y]=x;
	 else tata[x]=y;
	 if(rang[x]==rang[y]) rang[y]++;
}

int main(){
	fi>>n>>m;
	for(i=1;i<=m;i++){
		fi>>e[i].x>>e[i].y>>e[i].cost;
	}
	
	sort(e+1,e+m+1,comp);

	for(i=1;i<=n;i++){
		tata[i]=i;
		rang[i]=0;
	}
	
	for(i=1;i<=m;i++){
		int x = e[i].x;
		int y = e[i].y;
		int radx = radacina(x);
		int rady = radacina(y);
		
		if(radx!=rady){
			uneste(radx,rady);
			sol += e[i].cost;
			solm[++nr_m]=i;
		}	
	}
	
	fo<<sol<<"\n";
	fo<<nr_m<<"\n";
	for(i=1;i<=nr_m;i++) fo<<e[solm[i]].x<<" "<<e[solm[i]].y<<"\n";	
	
	fi.close();
	fo.close();
	return 0;
}