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

struct muchie{
	int n1,n2,cost;
};
muchie graf[400008], apm[200008];
int t[200008], h[200008];
int cmp(muchie a, muchie b)
{
	return(a.cost < b.cost);
}

int root(int x)
{
	while (t[x]!=0)
		x = t[x];
	return x;
}

int main()
{
	ifstream f("apm.in");
	ofstream g("apm.out");
	int n,m;
	f >> n >> m;

	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[200000];
	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;
		int rx = root(x);
		int ry = root(y);
		if(rx!=ry){
			ct++;
			apm[ct]=graf[i];
			cost+=graf[i].cost;
			//int val=c[x];	replace(c+1,c+n+1,val,c[y]);
			if (h[rx] > h[ry])
				t[ry] = rx;
			else
				if (h[rx] < h[ry])
					t[rx] = ry;
				else
				{
					t[ry] = rx;
					h[rx]++;
				}
		}
		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";

}