#include <iostream>
#include <fstream>
using namespace std;
#define infinit 2000000000
struct arbore
{
    int l,c,val;
} arb[100000];
int t[10000],s[100000],c,n,m;
void citire()
{
    ifstream in("apm.in");
    int i;
    in>>n>>m;
    for(i=1; i<=m; i++)
        in>>arb[i].l>>arb[i].c>>arb[i].val;
}
int cost(int linie, int col)
{
    for(int i=1; i<=m; i++)
        if((arb[i].l==linie and arb[i].c==col) or(arb[i].l==col and arb[i].c==linie))
            return arb[i].val;
    return infinit;
}
void apm()
{
    int ns,i,k,minim,tata,fiu,cst,cv,cn;
    ns=1;
    for(i=1; i<=n; i++)
        s[i]=ns;
    s[ns]=0;
    for(k=1; k<n; k++)
    {
        minim=infinit;
        for(i=1; i<=n; i++)
        {
            cst=cost(i,s[i]);
            if(s[i]!=0)
                if(cst!=0 and cst<minim)
                {

                    minim=cst;
                    //cout<<i<<" "<<s[i]<<" "<<minim<<endl;
                    tata=s[i];
                    fiu=i;
                }
        }
        s[fiu]=0;
        t[fiu]=tata;
        c=c+minim;
        for(i=1; i<=n; i++)
            if(s[i]!=0)
            {
                    cn=cost(i,fiu);
                    cv=cost(i,s[i]);
                if(cv!=0)
                    if(cv>cn)
                        s[i]=fiu;
            }
    }
}
int main()
{
    ofstream out("apm.out");
    int i;
    citire();
    apm();
    out<<c<<endl;
    out<<n-1<<endl;
    for(i=2;i<=n;i++)
        out<<t[i]<<" "<<i<<endl;
    return 0;
}