#include<stdio.h>
#include<vector>
#define Nmax 200010
#define Inf 1<<30
#define pb push_back
#define mp make_pair
using namespace std;

int T[Nmax],h[Nmax],C[Nmax],i,n,m,poz[Nmax],Arb[Nmax],a,b,c,Cost,K;
vector < pair <int , int > > V[Nmax];

void swap(int i, int j)
{
	int aux;
	poz[h[i]]=j;
	poz[h[j]]=i;
	aux=h[i]; h[i]=h[j]; h[j]=aux;
}

int pozmin(int i)
{
	if( (i<<1) + 1 <= K)
		if( C[h[(i<<1)+1]] < C[h[i<<1]] ) return (i<<1)+1;
	return i<<1;
}

void down(int i)
{
	int k;
	if(i <= (K>>1) )
	{
		k=pozmin(i);
		if(C[h[k]]<C[h[i]])
		{
			swap(i,k);
			down(k);
		}
	}
}

void up(int i)
{
	if(i>1)
	{
		if(C[h[i]]<C[h[i>>1]])
		{
			swap(i,i>>1);
			up(i>>1);
		}
	}
}

void push(int nod)
{
	h[++K]=nod;
	poz[nod]=K;
	up(K);
}

void pop()
{
	swap(1,K);
	poz[h[K]]=0;
	h[K]=0;
	K--;
	down(1);
}
int next()
{
	if(K>0) return h[1];
	return 0;
}


void apm(int nod)
{
	if(!nod) return ;
	
	int N=V[nod].size(),fiu,i,cost;
	
	for(i=0;i<N;i++)
	{
		fiu=V[nod][i].first;
		cost=V[nod][i].second;
		
		if( T[fiu] )
		{
			if(C[fiu] > cost)
			{
				T[fiu]=nod;
				if(C[fiu]==Inf) { C[fiu]=cost; push(fiu); continue;}
				C[fiu]=cost;
				up(poz[fiu]);
			}
		}
	}
	nod=next();
	Arb[nod]=T[nod];
	T[nod]=0;
	Cost+=C[nod];
	pop();
	apm(nod);
}

int main()
{
	freopen("apm.in","r",stdin);
	freopen("apm.out","w",stdout);
	
	scanf("%d %d",&n,&m);
	
	for(i=1;i<=m;i++)
	{
		scanf("%d %d %d",&a,&b,&c);
		V[a].pb(mp(b,c));
		V[b].pb(mp(a,c));
	}
	
	for(i=2;i<=n;i++)
	{
		C[i]=Inf;
		T[i]=1;
	}
	
	apm(1);
	
	printf("%d\n%d\n",Cost,n-1);
	
	for(i=2;i<=n;i++)
		printf("%d %d\n",i,Arb[i]);
	return 0;
}