#include <fstream>
#include <iostream>
#include <algorithm>
#define nmax 200010
#define mmax 400010

using namespace std;

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

struct muchie{
	int x,y;
	int cost;
};
int rang[nmax];
int grupa[nmax];
muchie mdate[mmax];
int muchii[mmax];
int solutie[nmax];

int find(int x){
	int r;
	for (r=x;grupa[r]!=r;r=grupa[r]);
	return r;
}

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

bool cmp(int x, int y) {
	return mdate[x].cost<mdate[y].cost;
}


int main(){
	int i;
	int n,m;
	in>>n>>m;
	for (i=1;i<=m;i++){
		in>>mdate[i].x>>mdate[i].y>>mdate[i].cost;
	}
	for (i=1;i<=n;i++){
		rang[i]=1;
		grupa[i]=i;
	}
	for (i=1;i<=m;i++){
		muchii[i]=i;
	}
	sort(muchii+1,muchii+1+m,cmp);//sortez muchiile dupa cost

	int rez=0;
	int nr=0;
	for (i=1;i<=m;i++){//parcurgi muchiile  in ordine costului si adaugi daca nu e ciclu adica daca nu sunt in aceeasi grupa
		int a,b;
		a=find(mdate[muchii[i]].x);
		 b=find(mdate[muchii[i]].y);
	
		if (a!=b){
			unite(a,b);	
			rez+=mdate[muchii[i]].cost;
			++nr;
			solutie[nr]=muchii[i];
		}
			
	}
	out<<rez<<"\n"<<nr<<"\n";
	for (i=1;i<=nr;i++){
		out<<mdate[solutie[i]].x<<" "<<mdate[solutie[i]].y<<"\n";
	}
		return 0;
	}