#include <iostream>
#include <stdio.h>
#include <conio.h>

using namespace std;

int weight[20][20],visited[20],d[20],p[20];
int n,m;


 FILE *in,*out;



void citire()
{
    in=fopen("apm.in","r");
 int i,j,a,b,w;
  fscanf(in,"%d%",&n);
 fscanf(in,"%d",&m);
 for(i=1;i<=n;i++)
   for(j=1;j<=n;j++)
     weight[i][j]=0;
 for(i=1;i<=n;i++)
 {
   p[i]=visited[i]=0;
   d[i]=32767;
 }
 for(i=1;i<=m;i++)
 {
   fscanf(in,"%d %d %d",&a,&b,&w);
   weight[a][b]=weight[b][a]=w;
 }

 }

 void prim()
 {
  out=fopen("apm.out","w");
 int current,totalvisited,mincost,i;
 current=1;d[current]=0;
 totalvisited=1;
 visited[current]=1;
 while(totalvisited!=n)
 {
   for(i=1;i<=n;i++)
   {
     if(weight[current][i]!=0)
       if(visited[i]==0)
     if(d[i]>weight[current][i])
     {
       d[i]=weight[current][i];
       p[i]=current;
     }
   }
   mincost=32767;
   for(i=1;i<=n;i++)
   {
     if(visited[i]==0)
       if(d[i]<mincost)
       {
     mincost=d[i];
     current=i;
       }
   }
   visited[current]=1;
   totalvisited++;
 }
 mincost=0;
 for(i=1;i<=n;i++)
   mincost+=d[i];

    fprintf(out,"%d\n",mincost);

 int m2=0;
 for(i=1;i<=n;i++)
        if(p[i]!=0) m2++;

    fprintf(out,"%d\n",m2);
 for(i=1;i<=n;i++)
       if(p[i]!=0) fprintf(out,"%d %d\n",i,p[i]);

 }

 main()
 {
 citire();
 prim();
 fclose(in);
 fclose(out);
 getch();

 return 0;
 }