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

struct muchie{
	int n1,n2,cost;
};

int cmp(muchie a, muchie b)
{
	return(a.cost < b.cost);
}

int main()
{
	ifstream f("apm.in");
	ofstream g("apm.out");
	int n,m;
	f >> n >> m;
	
	muchie graf[6000], apm[100];

	for(int i=1;i<=m;i++){
		f >> graf[i].n1 >> graf[i].n2 >> graf[i].cost;
	}

	sort(graf+1,graf+m+1,cmp);

	int c[100];
	for(int i=1;i<=n;i++){
		c[i]=i;
	}

	int ct=0, cost=0;;

	for(int i=1;i<=m;i++){
		int x=graf[i].n1;
		int y=graf[i].n2;
		if(c[x]!=c[y]){
			ct++;
			apm[ct]=graf[i];
			cost+=graf[i].cost;
			int val=c[x];
			replace(c+1,c+n+1,val,c[y]);
		}
		if(ct==n-1){
			break;
		}
	}

	g<<cost<<endl;
	g<<n-1<<endl;
	for(int i=1;i<=ct;i++)
		g<<apm[i].n1<<" "<<apm[i].n2<<"\n";

}