#include <iostream>
#include <fstream>
using namespace std;

long l[100],nrm,ct,n,m;

struct muchie {
    long x,y,c;
}v[400000],aux,t[400000];

void citire()
{
    long i;
    ifstream f ("apm.in");
    f>>n>>m;
    for (i=1;i<=m;i++)
        f>>v[i].x>>v[i].y>>v[i].c;
}
void ordo ()
{
    long i,j;
    for (i=1;i<m;i++)
        for (j=i+1;j<=m;j++)
            if (v[i].c>v[j].c)
            {
                aux=v[i];
                v[i]=v[j];
                v[j]=aux;
            }
}
void apm_kruskal()
{
    long i,k,nr1,nr2,j;
    ordo();
    for (j=1;j<=n;j++)
        l[j]=j;
    ct=0;k=0;i=1;
    while (i<=m)
    {
        if (l[v[i].x]!=l[v[i].y])
        {

            nrm++;
            t[nrm].x=v[i].x;
            t[nrm].y=v[i].y;
            //cout<<"("<<v[i].x<<","<<v[i].y<<")"<<" ";
            ct+=v[i].c;
            nr1=l[v[i].x];
            nr2=l[v[i].y];
            k=nr1;
            for (j=1;j<=n;j++)
                if (l[j]==nr2)
                    l[j]=nr1;
        }
        i++;
    }
    ofstream g ("apm.out");
    g<<ct<<endl;
    g<<nrm<<endl;
    for (int i=1;i<=nrm;i++)
        g<<t[i].x<<" "<<t[i].y<<endl;
        g.close();
}

int main ()
{
    citire();
    apm_kruskal();
    return 0;
}