//determinare arbore partial de cost minim(APM)- algoritmul lui kruskal
#include<iostream>
#include<fstream>
using namespace std;

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

int n,m,cc[100],ct;

struct muchie{
	int x,y,c;
};

muchie v[400001],h[200001];

void citire(){
	in>>n>>m;
	for(int i=1; i<=m; i++)
		in>>v[i].x>>v[i].y>>v[i].c;
}

void ord(){
	for(int i=1; i<m; i++)
		for(int j=i+1; j<=m; j++)
			if(v[i].c > v[j].c){
				muchie aux=v[i];
				v[i]=v[j];
				v[j]=aux;
			}
}

void apm(){
	for(int i=1; i<=n; i++)
		cc[i]=i;
	int msel=0,i=1;
	while(msel<n-1){
		while( cc[v[i].x]== cc[v[i].y] )
			i++;
		msel++;
		h[msel]=v[i];
		ct+=v[i].c;
		int min=cc[v[i].x], max=cc[v[i].x];
		if(cc[v[i].y]>max)
			max=cc[v[i].y];
		if(cc[v[i].y]<min)
			min=cc[v[i].y];
		for(int j=1; j<=n; j++)
			if(cc[j]==max)
				cc[j]=min;
	}
}

int main(){
	citire();
	ord();
	apm();
	out<<ct<<endl;
	out<<n-1<<endl;
	for(int i=1; i<=n-1; i++)
		out<<h[i].x<<" "<<h[i].y<<endl;
	return 0;
}