#include<stdio.h>
#include<vector>
#include<string.h>
#define pb push_back
#define mp make_pair
#define inf 1000000000

using namespace std;

int main()
{
	int n,m,a,b,c,cost=0,prev[200001],key[200001],i,min=0,imin;
	vector< pair<int,int> > v[200001];
	char viz[200001];
	FILE *f=fopen("apm.in","r");


	fscanf(f,"%i%i",&n,&m);
	for(i=0;i<m;i++)
	{
		fscanf(f,"%i%i%i",&a,&b,&c);
		v[a].pb(mp(b,c));
		v[b].pb(mp(a,c));
	}
	fclose(f);

	
	memset(viz,0,sizeof(viz));
	key[1]=0;
	prev[1]=-1;
	for(i=2;i<=n;i++)
		key[i]=inf;

	for(;;)
	{
		min=inf;
		for(i=1;i<=n;i++)
		{
			if(viz[i]==0 && key[i]<min)
			{
				min=key[i];
				imin=i;
			}
		}
		if(min==inf)
			break;
		viz[imin]=1;
		cost+=min;
		for(i=0;i<(int) v[imin].size();i++)
		{
			if(viz[v[imin][i].first]==0 && v[imin][i].second<key[v[imin][i].first])
			{
				prev[v[imin][i].first]=imin;
				key[v[imin][i].first]=v[imin][i].second;
			}
		} 
	}
	f=fopen("apm.out","w");
	fprintf(f,"%i\n",cost);
	fprintf(f,"%i\n",n-1);
	for(i=2;i<=n;i++)
		fprintf(f,"%i %i\n",prev[i],i);
	fclose(f);
	return 0;
}