#include<cstdio>
#include<algorithm>

using namespace std;

#define Nmax 200001

#define Mmax 400001

struct muchie {
	int x, y, c;
} G[Mmax];

int N, M, T[Nmax], sol[Mmax], cost, X;

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

int get_root(int x) {
	while(T[x]!=x)
		x=T[x];
	return x;
}

int main() {
	freopen("apm.in","r",stdin);
	freopen("apm.out","w",stdout);
	
	int i, j, k, c, root1, root2;
	scanf("%d %d",&N,&M);
	for(i=1; i<=M; i++)
		scanf("%d %d %d",&G[i].x,&G[i].y,&G[i].c);
	sort(G+1,G+M+1,cmp);
	for(i=1; i<=N; i++)
		T[i]=i;
	
	for(k=1; k<=M; k++) {
		i=G[k].x; j=G[k].y; c=G[k].c;
		root1=get_root(i);
		root2=get_root(j);
		if(root1==root2)
			continue;
		if(root1>root2) 
			T[root1]=T[root2];
		else
			T[root2]=T[root1];
		cost+=c;
		sol[++X]=i;
		sol[++X]=j;
	}
	printf("%d\n%d\n",cost,N-1);
	for(i=1; i<=X; i+=2)
		printf("%d %d\n",sol[i],sol[i+1]);
	
	return 0;
}