#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;
}

void reuneste(int i, int j) {
	int k;
	i=T[i]; j=T[j];
	if(i==j)
		return;
	for(k=1; k<=N; k++)
		if(T[k]==i)
			T[k]=j;
}

int main() {
	freopen("apm.in","r",stdin);
	freopen("apm.out","w",stdout);
	
	int i, j, k, c;
	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;
		if(T[i]==T[j]) 
			continue;
		reuneste(i,j);
		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;
}