#include <iostream>
#include <fstream>
#define INF 1000000000
using namespace std;

int c[100][100],T[100],Q[100],n;
ifstream f("apm.in");
ofstream g("apm.out");

void citire_graf()
{
	int m,x,y,z;

	f>>n;
	f>>m;

	for(int i=1 ; i <= n ; i++)
		for(int j=1 ; j <= n ; j++)
			c[i][j]=INF;

	for(int i=1 ; i <= n ; i++)
		c[i][i]=0;

	for(int i=1 ; i <= m ; i++)
	{
        f>>x>>y>>z;
		c[x][y]=z;
		c[y][x]=z;
	}
}
void creare_apm()
{
    int ar[n*2][3];
    int V[100],minim,w,cost=0,muchii=0;

	for(int i=2 ; i <= n ; i++)
        V[i]=i;  //varfurile neincluse in arbore
	V[1]=0;

	for(int i=2 ; i <= n ; i++)
	{
	    T[i]=1;
        Q[i]=c[1][i];
	}

	while(1)
	{
	    minim=INF;  //determinam muchia de cost minim

		for(int i=2 ; i <= n ; i++)
			if(V[i] && Q[i]<minim)
			{
			    minim=Q[i];
                w=i;
			}

		if(minim == INF)
            break;

        V[w]=0;  //varful w a fost inclus in arbore
        ar[muchii][1]=T[w];
        ar[muchii][2]=w;//muchia adaugata
        muchii++;
        cost=cost + c[T[w]][w];  //actualizam costul arborelui

        for(int j=2 ; j <= n ; j++)
            if(V[j] && Q[j] > c[w][j])
            {
                T[j]=w;
                Q[j]=c[w][j];
            }
	}

	g<<cost<<endl;
    g<<muchii<<endl;

    for(int i=0 ; i < muchii ; i++)
        g<<ar[i][1]<<" "<<ar[i][2]<<endl;
}
int main()
{
    citire_graf();
	creare_apm();
	return 0;
}