#include <fstream>
#include <algorithm>
#define NMAX 200002
#define MMAX 4000002
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
struct muchie {int x,y,c;};
muchie G[MMAX];
int n,m,cost;
int conex[NMAX];
int a[NMAX];///indicii muchiilor selectate in arbore
///conex[i] este comp conexa din care face parte i
void citire();
void kruskal();
void afisare();
void sortare();
bool compar(muchie a, muchie b)
///returneaza 1(true) daca Muchia a rebuie sa fie inaintea Muchiei b in vectorul sortat
{
    return a.c<b.c;
}

int main()
{
    citire();
    kruskal();
    afisare();
    return 0;
}
void citire()
{
 fin>>n>>m;
 int i;
 for(i=1;i<=m;i++)
     fin>>G[i].x>>G[i].y>>G[i].c;
}
void kruskal()
{
 ///ordonez muchiile crescator dupa cost
 ///sortare();
 sort(G+1,G+m+1, compar);
 int i,nrsel,cx,cy,j;
 for(i=1;i<=n;i++)
     conex[i]=i;
 nrsel=0;
 i=1;
 while(nrsel<n-1)
       {
         if(conex[G[i].x]!=conex[G[i].y]) ///nu formeaza ciclu
        {
         nrsel++;
         a[nrsel]=i;
         cost+=G[i].c;
         ///unificam componentele conexe ale extremitatilor
         cx=conex[G[i].x];
         cy=conex[G[i].y];
         for(j=1;j<=n;j++)
             if(conex[j]==cy)
                conex[j]=cx;
        }
        i++;
       }
}
void sortare()
{
 int i,schimb;
 muchie aux;
 do{
   schimb=0;
 for(i=1;i<m;i++)
     if(G[i].c>G[i+1].c)
        {
         aux=G[i];
         G[i]=G[i+1];
         G[i+1]=aux;
         schimb=1;
        }

 }
 while(schimb);
}
void afisare()
{
 int i;
 fout<<cost<<'\n';
 fout<<n-1<<'\n';
 for(i=1;i<n;i++)
     fout<<G[a[i]].x<<" "<<G[a[i]].y<<'\n';
 fout.close();
}