#include <iostream>
#include <fstream>
#define MAXIM 2000000000
#define MaxN 2000
#define MaxM 400000
using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");
int n,m,mat[MaxN][MaxN],cost,s[MaxN],T[MaxN];
void APM()
{
    int i,j,k,ns,mini;
    ns=1;
    for(i=1;i<=n;i++)
        s[i]=ns;
    s[ns]=0;
    for(k=2;k<=n;k++)
    {
        mini=MAXIM;
        for(i=1;i<=n;i++)
            if(s[i])
                if(mat[i][s[i]]<mini)
                {
                    mini=mat[i][s[i]];
                    j=i;
                }
        T[j]=s[j];s[j]=0;
        cost+=mini;
        for(i=0;i<=n;i++)
            if(s[i])
            if(mat[i][j]<mat[i][s[i]])
                    s[i]=j;

}
}
int main()
{ int a,b,c,i;
in>>n>>m;
for(i=1;i<=m;i++)
{
    in>>a>>b>>c;
    if(mat[a][b]!=0){if(mat[a][b]>c){mat[a][b]=c;
    mat[b][a]=c; } }
    else{mat[a][b]=c;
    mat[b][a]=c; }
  }
  for(i=1;i<=n;i++)
    for(a=1;a<=n;a++)
        if(mat[i][a]==0)mat[i][a]=200000000;

APM();
out<<cost<<"\n";
out<<n-1<<"\n";
for(i=2;i<=n;i++)
    out<<T[i]<<" "<<i<<"\n";

        return 0;
}