#include <iostream>
#include <fstream>
#define MAXIM 2000
using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");
int n,m,mat[200000][200000],viz[200000],T[20000000],C[200000],ma,k=1;
void APM()
{ int i,j,mini,a,a1;
    viz[1]=1;

    while(k<n)
    {mini=MAXIM;
        for(i=1;i<=n;i++)
           for(j=1;j<=n;j++)
            if(viz[i]==1)
                if(viz[j]==0)
                   if(mat[i][j]!=0)
                     if(mat[i][j]<mini)
        {                   mini=mat[i][j];
                                a=i;
                                a1=j;
            }

         viz[a1]=1;
         T[a1]=a;
         C[a1]=mini;
         ma=ma+mini;
       k++;
    }
}
int main()
{ int a,b,c,i;
in>>n>>m;
for(i=1;i<=m;i++)
{
    in>>a>>b>>c;
    mat[a][b]=c;
    mat[b][a]=c;
}

in.close();
APM();
out<<ma<<"\n";
out<<k-1<<"\n";
for(i=2;i<=n;i++)
    out<<T[i]<<" "<<i<<endl;


    out.close();
        return 0;
}