#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 pmin(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=pmin(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(),son,i,cost;

	for(i=0;i<N;i++)
	{
		son=V[nod][i].first;
		cost=V[nod][i].second;

		if( T[son] )
		{
			if(C[son] > cost)
			{
				T[son]=nod;
				if(C[son]==Inf) { C[son]=cost; push(son); continue;}
				C[son]=cost;
				up(poz[son]);
			}
		}
	}
	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;
}