#include <iostream>
#include <fstream>
#define nmax 20000
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
int n,m, c[nmax][nmax], viz[nmax], tata[nmax], ctot, nr;

void citire()
{
    int i,j,x,y,k;
    f>>n>>m;

    for(i=1; i<=n; i++)
        for(j=1; j<=n; j++)
        if(i!=j)
        c[i][j]=1e9;

    for(i=1; i<=m; i++)
    {
        f>>x>>y>>k;
        c[x][y]=k;
        c[y][x]=k;
    }
}

void prim()
{
    int i,j,k,mn,s,d;
    for(i=1; i<=n; i++)
    {
        viz[nmax]=0;
        tata[nmax]=0;
    }
    viz[1]=1;
    ctot=0;
    for(k=1; k<n; k++)
    {
        mn=1e9;
        for(i=1; i<=n; i++)
        for(j=1; j<=n; j++)
            if(viz[i]==1 && viz[j]==0 && c[i][j]<mn)
            {
                s=i;
                d=j;
                mn=c[i][j];
            }
        viz[d]=1;
        tata[d]=s;
        ctot+=c[s][d];
    }
}

int main()
{
    citire();
    prim();
    g<<ctot<<"\n"<<n-1<<"\n";
    int i;
    for(i=2; i<=n; i++)
        g<<i<<' '<<tata[i]<<"\n";
    f.close();
    g.close();
    return 0;
}