#include <iostream>
#include <fstream>

using namespace std;

///Determina un arbore partial de cost minim pentru un graf conex de costuri

ifstream f("apm.in");
ofstream g("apm.out");
int a[20][20],n,m, pinf=1000;
int s[20], t[20], cost;

void read()
{
    int i,j,x,y,c;
    f>>n>>m;
    for(i=1; i<=n; i++)
        for(j=1; j<=n; j++)
            a[i][j]=pinf;
   for(i=1;i<=m;i++)
   {f>>x>>y>>c;
        a[x][y]=a[y][x]=c;}
}

void print()
{
    int i,j;
    for(i=1; i<=n; i++)
    {
        for(j=1; j<=n; j++)
            cout<<a[i][j]<<" ";
        cout<<endl;
    }
}
int minim()
{
    int i, minim=pinf, nod;
    for(i=1; i<=n; i++)
        if(s[i]!=0)
            if(a[i][s[i]]<minim)
            {
                minim=a[i][s[i]];
                nod=i;
            }
    return nod;

}
void update_s(int nod)
{
    int i;
    for(i=1; i<=n; i++)
        if(s[i]!=0)
            if(a[i][s[i]]>a[i][nod])
                s[i]=nod;

}
void build_tree(int root)
{
    int i, nod;
    for(i=1; i<=n; i++)
        if(i!=root)
            s[i]=root;
    for(i=1; i<=n-1; i++)
    {
        ///nod=minim; retin nodul pt care muchia e de cost minim [i][s[i]]
        nod=minim();
        ///actualizez cost cost+=a[i][s[i]]
        cost+=a[nod][s[nod]];
        ///t[i]=s[i]; s[i]=0;
        t[nod]=s[nod];
        s[nod]=0;
        ///actualizez s prin nodul nod daca avem distante mai scurte
        update_s(nod);
    }
}

int main()
{
    read();
    //print();
    build_tree(1);
    g<<cost<<endl;
    g<<n-1<<endl; ///nr muchii
    ///afisare muchii
    int i;
    for(i=2;i<=n;i++)
    g<<i<<" "<<t[i]<<endl;

    return 0;
}