#include <iostream>
#include <fstream>
#define MAXIM 2000
using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");
int ns,n,m,mat[20000][20000],viz[20000],T[20000],C[20000],minim;
void APM()
{ int i,k,j,mini,r;
    viz[ns]=1;
   for(k=1;k<n;k++)
   {    for(i=1;i<=n;i++)
        {   mini=9000;
                for(j=1;j<=n;j++)
                if(viz[j]==0)
                if(mat[i][j]!=0)
                if(viz[i]==1)
                if(mat[i][j]<mini)
                    {
                        mini=mat[i][j];
                        r=j;
                    }
        if(mini!=9000)
        {   viz[r]=1;
        T[r]=i;
        C[r]=mini;
        }
        }
   }
}
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;
}
ns=1;
in.close();
APM();
for(i=1;i<=n;i++)
{minim=minim+C[i];

}
out<<minim<<endl;
out<<n-1<<endl;
for(i=2;i<=n;i++)
    out<<i<<" "<<T[i]<<endl;
out<<endl;

        return 0;
}