#include <fstream>
#include<stdio.h>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
long int a[20001][20001];
typedef struct {
	int x;
	int y;
	int c;
}muchie;
muchie u[50];
void sortare (int m)
{
    long int i,j;
	muchie aux;
	for(i=1;i<=m-1;i++)
		for(j=i+1;j<=m;j++)
			if(u[i].c>=u[j].c){
			aux=u[i];u[i]=u[j];u[j]=aux;
			}
}
void matrice (int m)
{
	long int z,k,i;
	for(i=1;i<=m;i++){
		f>>u[i].x>>u[i].y;
		f>>u[i].c;
	}
}
int prim(int n, int m)
{
	long int ct,j,viz[50],i,k,w=0,S[20001],O[20001],l=1;
	for(j=1;j<=n;j++)viz[j]=0;
	viz[u[1].x]=1;viz[u[1].y]=1;ct=u[1].c;
	w++;S[l]=u[1].x;O[l]=u[1].y;
	for(k=1;k<n-1;k++){
		for(i=2;i<=m;i++)
		{
			if(viz[u[i].x]+viz[u[i].y]==1)
			{
				w++;l++;S[l]=u[i].x;O[l]=u[i].y;
				if(viz[u[i].x]==1)viz[u[i].y]=1;
				else viz[u[i].x]=1;
				ct+=u[i].c;
				i=m+1;
			}
		}
	}
	g<<ct;g<<endl;
	g<<w<<endl;
	for(i=1;i<=l;i++)
	{
	    g<<S[i]<<" "<<O[i]<<endl;
	}
    return 0;
}
int main()
{
	long int n,m;
	f>>n;
	f>>m;
	matrice (m);
	sortare (m);
	prim (n,m);
	g<<endl;
	return 0;
}