#include <iostream>
#include <fstream>
#define MAXIM 200000200
using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");

int n,m,A[400001],B[400001],C[400001],t[400001],s[400001];
long int minim=0;
int da_cost(int a, int b)
{
    int i;
    for(i=1;i<=m;i++)
    {
        if(A[i]==a && B[i]==b) return C[i];
        if(A[i]==b && B[i]==a) return C[i];
    }
    return MAXIM;
}
void APM()
{
    int i,k,j,mini,ns, cost, cv,cn;
    ns=1;
    for(i=1;i<=n;i++)
        s[i]=ns;
    s[ns]=0;
    for(k=1;k<n;k++)
    {
        mini=MAXIM;
        for(i=1;i<=n;i++)
            if(s[i])
            {
                cost=da_cost(i,s[i]);
                //out<<"Cost "<<i<<" "<<s[i]<<" "<<cost<<endl;
                if(cost<mini)
                {
                    mini=cost;
                    j=i;
                }
            }
        t[j]=s[j];
        minim=minim+mini;
        s[j]=0;
        for(i=1;i<=n;i++)
            if(s[i])
            {
                cv=da_cost(i,s[i]);
                cn=da_cost(i,j);
                if(cv>cn)
                    s[i]=j;
            }
    }
}
int main()
{
    int a,b,c,i,j;
    in>>n>>m;
    for(i=1;i<=m;i++)
    {
        in>>a>>b>>c;
        A[i]=a;
        B[i]=b;
        C[i]=c;
    }
    in.close();
    APM();
    out<<minim<<"\n";
    out<<n-1<<"\n";
    for(i=2;i<=n;i++)
        out<<t[i]<<" "<<i<<"\n";
    in.close();
    out.close();
    return 0;
}