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

int n,m,mat[20000][20000],t[20000],s[20000];
long int minim=0;

void APM()
{
    int i,k,j,mini,r,q,ns;
    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])
                if(mat[s[i]][i]<mini)
                {
                    mini=mat[s[i]][i];
                    j=i;
                }
        t[j]=s[j];
        minim=minim+mini;
        s[j]=0;
        for(i=1;i<=n;i++)
            if(s[i] && mat[i][s[i]]>mat[i][j])
                s[i]=j;
    }
}
int main()
{
    int a,b,c,i,j;
    in>>n>>m;
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            mat[i][j]=MAXIM;
    for(i=1;i<=n;i++)
        mat[i][i]=0;
    for(i=1;i<=m;i++)
    {
        in>>a>>b>>c;
        mat[a][b]=c;
        mat[b][a]=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;
}