//Arbore partial de cost minim. Algoritmul Kruskal.
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;

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

bool cmp(muchie A, muchie B)
{
	return (A.cost<B.cost);
}

muchie M[400005],K[400005];
int C[200005], H[200005];

int getRoot(int x){
	while(C[x]){ x=C[x]; }
	return x;
}

int main()
{
	ifstream f("apm.in");  //apm.in
	ofstream g("apm.out");

	int n,m;
	f >> n >> m;
	for(int i=1;i<=m;i++){
		f >> M[i].x >> M[i].y >> M[i].cost;
	}
	
	for(int i=1;i<=n;i++){
		C[i]=H[i]=0;
	}

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

	int ct=0; int cost=0;
	for(int i=1;i<=m;i++){
		int x=M[i].x;
		int y=M[i].y;

		int rx=getRoot(x);
		int ry=getRoot(y);

		if(rx!=ry){
			cost+=M[i].cost;
			K[++ct]=M[i];
			if(H[rx]>H[ry]){
				C[ry]=rx;
			}else if(H[rx]<H[ry]){
						C[rx]=ry;
					}else{
						C[rx]=ry;
						H[ry]++;
					}
		}
		if(ct==n-1) break;
	}

	g << cost << "\n";
	g << n-1 << "\n";
	for(int i=1;i<=n-1;i++){
		g << K[i].x << " " << K[i].y << " " << "\n";
	}
	

}