#include<stdio.h>
#include<algorithm>
#include<vector>

#define maxn 200005
#define maxedges 400005

using namespace std;

FILE*f=fopen("apm.in","r");
FILE*g=fopen("apm.out","w");

int n,m;
int T[maxn],Rg[maxn];
pair< int , pair<int,int> >M[maxedges];
vector<int>sol;

inline void unify ( const int &r1 , const int &r2 ){
	
	if ( Rg[r1] > Rg[r2] ){
		T[r2] = r1;
	}
	else{
		T[r1] = r2;
	}
	
	if ( Rg[r1] == Rg[r2] ){
		++Rg[r2];
	}
}

inline int root ( int x ){
	
	int R;
	for ( R = x ; T[R] != R ; R = T[R] );
	
	while ( T[x] != x ){
		int aux = T[x];
		T[x] = R;
		x = aux;
	}
	
	return R;
}

int main () {
	
	fscanf(f,"%d %d",&n,&m);
	for ( int i = 1 ; i <= m ; ++i ){
		fscanf(f,"%d %d %d",&M[i].second.first,&M[i].second.second,&M[i].first);
	}
	
	sort(M+1,M+m+1);
	
	for ( int i = 1 ; i <= n ; ++i ){
		T[i] = i;
		Rg[i] = 1;
	}
	
	int cost = 0;
	for ( int i = 1 ; i <= m ; ++i ){
		int x = M[i].second.first,y = M[i].second.second,c = M[i].first;
		
		if ( root(x) != root(y) ){
			cost += c;
			unify(root(x),root(y));
			sol.push_back(i);
		}
	}
	
	fprintf(g,"%d\n%d\n",cost,n-1);
	for ( int i = 0 ; i < n-1 ; ++i ){
		fprintf(g,"%d %d\n",M[sol[i]].second.first,M[sol[i]].second.second);
	}
	
	fclose(f);
	fclose(g);
	
	return 0;
}