#include <fstream>
#include <iostream>
using namespace std;
ifstream fin ("apm.in");
ofstream fout ("apm.out");

struct ar
{
       int x;
       int y;
       int n;
};
ar u[100];
int co[199999][2];


int main ()
{ 
     int n,i,j,pivot,l[200000]={0},ct=0,m,n1,n2,p=0,k;
     fin >>m>>n;
      
     for (i=1;i<=n;i++)
     
         fin >> u[i].x>>u[i].y>> u[i].n;
         i=1;
    for (i=1;i<=n-1;i++)
        for (j=1; j<=n-i;j++)
        if (u[j].n>u[j+1].n)
           {
                          pivot=u[j+1].n;
                          u[j+1].n=u[j].n;
                          u[j].n=pivot;
                          pivot=u[j+1].x;
                          u[j+1].x=u[j].x;
                          u[j].x=pivot;
                          pivot=u[j+1].y;
                          u[j+1].y=u[j].y;
                          u[j].y=pivot;  
                            
           }    
            
    for (i=1;i<=n;i++)
        l[i]=i;
 i=1;
 cout<<n;
    while (k<m-1)
       {
              cout << n; 
              if (l[u[i].x]!=l[u[i].y])
                 {
                   p++;
                   co[p][1]=u[i].x;
                   co[p][2]=u[i].y;                
                   n1=l[u[i].x];
                   n2=l[u[i].y];
                   k++;
                   
                   for (j=1;j<=n;j++)
                       if (l[j]==n2 )
                          l[j]=n1;                  
                   ct=u[i].n+ct;
                   
                 } 
                 i++;
               
       }
    fout << ct<<"\n";
    fout << m-1<<"\n";
    for (i=1;i<=p;i++)
    fout<< co[i][1]<<" "<<co[i][2]<<"\n";
    fin.close();
    fout.close();
               
}