#include<fstream>
#include<iostream>
using namespace std;
//cc - sir componente conexe
//sirmuchii - sirul de muchii alese
//suma - suma totala pe arbore
// n noduri , nr muchii
// m- sirul de muchii initial, citit fisier
struct muchie{int c1,c2,cost;};
muchie m[5001],aux;
int sirmuchii[5001],n,nr,cc[101],suma;
ifstream f("kruskal.in");
ofstream g ("kruskal.out");
void citire()
{ int i,j,k,cost;
  f>>n>>nr;
  for(i=1;i<=nr;i++)
    { f>>m[i].c1>>m[i].c2>>m[i].cost;
    }
    //oronez dupa costuri
    for(i=1;i<=nr-1;i++)
        for(j=i+1;j<=nr;j++)
        if(m[i].cost>m[j].cost)
    {aux=m[i];
        m[i]=m[j];
        m[j]=aux;
    }
// fiecare nod in componenta diferita
 for(i=1;i<=n;i++)
    cc[i]=i;
}

void krusk()
{ int i,j=0,muchie,cmin, cmax,k;
//j contor pe sirul de muchii alese
for(i=1;i<=nr&&j<n-1;i++)
{    if(cc[m[i].c1]!=cc[m[i].c2]) // capete in cc diferite
 { j++;
 sirmuchii[j]=i;
 suma=m[i].cost+suma;
 //stabilesc nr de componenta minim, inlocuiesc apoi
 if( cc[m[i].c1]>cc[m[i].c2])
 {    cmin=cc[m[i].c2];
     cmax=cc[m[i].c1];
 }
 else
   {     cmin=cc[m[i].c1];
     cmax=cc[m[i].c2];
 }
 for(k=1;k<=n;k++)
 {if(cc[k]==cmax)
 cc[k]=cmin;
 }}}}

int main()
 { int i;citire();
 krusk();
 g<<suma<<endl << n - 1 << endl;
 for(i=1;i<=n-1;i++)
   g<<m[sirmuchii[i]].c1<<" "<<m[sirmuchii[i]].c2<<endl;
 }