#include <cstdio>
#include <algorithm>
#include <vector>
#define mx 400001
#define nx 200001

using namespace std;

int gr[nx]={0};
int nod1[mx], nod2[mx], cost[mx], it[mx];
int n,m,k;
int Ct[nx],cost_t=0;
vector <int> arb;


bool cmp (int a, int b)
{	return (cost[a]<cost[b]);
}

int grupa ( int a)
{
	int g=a,aux;
	while(gr[g]>0) g=gr[g];
	while( a!=g)
	{	aux=gr[a];
		gr[a]=g;
		a=aux;
	}
	return g;
}

void make_idem ( int a , int b)
{
	if(gr[a]<gr[b]) gr[b]=a;
	else 
	{	//if(gr[a]==gr[b]) --gr[b];
		gr[a]=b;
	}
}

int main()
{
	int i,j,a,b,c,muc=0;
	freopen("apm.in","r",stdin);
	freopen("apm.out","w",stdout);
	scanf("%d %d", &n, &m );
	for(i=0 ; i<m; ++i)
	{	scanf("%d %d %d", &nod1[i], &nod2[i], &cost[i]);
		it[i]=i;
	}
	

	sort (it, it+m, cmp);
	for( j=0, i=it[0] ; j<m; ++j, i=it[j])
	{	a= grupa( nod1[i] );
		b= grupa( nod2[i] );
		
		if( a != b ) 
		{
			Ct[muc++]=cost[i];
			cost_t+=cost[i];
			arb.push_back(i);
			make_idem( a, b );
		}
	}

	printf("%d\n%d\n", cost_t, n-1);
	for( i=arb.size()-1; i>=0; --i)
	     printf( "%d %d\n",nod1[arb[i]],nod2[arb[i]]);
    fclose(stdout);  
	return 0;
}