#include <fstream>
#include <algorithm>
#define NMAX 200000
#define MMAX 400000

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]; //conex[i] = componenta conexa din care face parte i
int A[NMAX]; //indicii muchiilor selectate in arbore

void sortare();
void citire();
void kruskal();
void afisare();
bool compar(Muchie a, Muchie b)
///return 1 daca muchia a trebuie sa fie inainte muchiei b in vectorul sortat
{
    return a.c<b.c;
}
int main()
{
    citire();
    kruskal();
    afisare();
    return 0;
}

void citire()
{int i;
    fin>>n>>m;
    for(i=1; i<=m; i++)
        fin>>G[i].x>>G[i].y>>G[i].c;
}
void kruskal()
{int i,j,cx,cy,nrsel;
    //ordonez muchiile crescator dupa cost
    //sortare();
    sort(G+1, G+m+1, compar);
    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 cicluri
         {
          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 schimb,i;
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();
}