#include <fstream>

using namespace std;

#define PInfinit 1.e20
long int n,m,s[200000],t[200000]; int  ctot,a[20000][20000];

ifstream fin("apm.in");
ofstream fout("apm.out");

void Citire()
{
    fin>>n; fin>>m;
    int i,j,c;
    for( i=1;i<=n;i++)
        for(j=1;j<=n;j++)
        {
            if(i==j) a[i][j]=0;
            else a[i][j]=PInfinit;
        }
    while(fin>>i>>j>>c) {a[i][j]=c; a[j][i]=c;}

}

void Alg()
{
    int min;
    s[1]=0; int j;
    for(int i=2;i<=n;i++)
       s[i]=1;
    for(int k=1;k<n;k++)
    {
        min=PInfinit;
        for(int i=1;i<=n;i++)
            if(s[i] && a[s[i]][i]<min)
            {
                min=a[s[i]][i];
                j=i;
            }
        t[j]=s[j]; ctot+=a[s[j]][j]; s[j]=0;
        for(int i=1;i<=n;i++)
            if(s[i] && a[s[i]][i]>a[j][i]) s[i]=j;
    }
}

void Afisare()
{
    fout<<ctot<<'\n'<<n-1<<'\n';
    for(int i=2;i<=n;i++) fout<<t[i]<<' '<<i<<'\n';
}

int main()
{
    Citire();
    Alg();
    Afisare();
}