#include<fstream>
#include<iostream>
using namespace std;


ifstream fin("apm.in");
ofstream fout("apm.out");
const int inf=1<<20;
int n,m,A[100][100],P[100],B[100];

void citire()
{    int i,j,k,c;
     fin>>n>>m; // nr noduri si arce
     for(i=1;i<n;i++) // citirea costurilor
        for(j=i+1;j<=n;j++)
            A[i][j]=A[j][i]=inf;
     for(int k=1;k<=m;k++)
        { fin>>i>>j>>c;
          A[i][j]=A[j][i]=c;
        }
}

int main()
{
    int cs=0,p=0;
    int i,j,k,minn,x,y;
    citire();
    P[1]=1;
    for(k=1;k<n;k++)
    {
       minn=inf;
       for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
           if(P[i] && !P[j] && A[i][j]<minn)
           {
               minn=A[i][j]; x=i;y=j;
           }
       p++;
       cs=cs+A[x][y];
       P[y]=1;

    }
    fout<<cs<<endl;
    fout<<p<<endl;
    B[1]=1;
    for(k=1;k<n;k++)
    {
       minn=inf;
       for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
           if(B[i] && !B[j] && A[i][j]<minn)
           {
               minn=A[i][j]; x=i;y=j;
           }
       fout<<x<<" "<<y<<" "<<endl;
       B[y]=1;
    }

    fin.close();
    fout.close();
    return 0;
}