#include <stdio.h>
#include <algorithm>
using namespace std;
#define NMAX 400005
int X[NMAX], Y[NMAX], P[NMAX], C[NMAX], sol[NMAX];
int T[NMAX/2], RG[NMAX/2];
int n, m;
bool compf(int a,int b){
	return C[a] < C[b];
}
int find(int x){
	if(x != T[x])
		T[x] = find(T[x]);
	return T[x];
}
void unite(int x,int y){
	if(RG[x] > RG[y])
		T[y] = x;
	else T[x] = y;
	if(RG[x] == RG[y])
		RG[x] ++;
}
int main(){
	freopen("apm.in", "r" ,stdin);
	freopen("apm.out", "w", stdout);
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; ++i)
		T[i] = i;
	for(int i = 1; i <= m; ++i){
		scanf("%d%d%d", &X[i], &Y[i], &C[i]);
		P[i] = i;
	}
	sort(P + 1, P + m + 1, compf);
	int c = 0;
	for(int i = 1; i <= m; ++i)
		if(find(X[P[i]]) != find(Y[P[i]])){
			c += C[P[i]];
			sol[++sol[0]] = i;
			unite(find(X[P[i]]), find(Y[P[i]]));
		}
	printf("%d\n%d\n", c, sol[0]);
	for(int i = 1; i <= sol[0]; ++i)
		printf("%d %d\n", X[P[sol[i]]], Y[P[sol[i]]]);
	return 0;
}