#include <fstream>
#include <algorithm>
#define NMAX 200002
#define MMAX 400002
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();
bool compar(muchie a,muchie b)
///returneaza 1 daca muchia a trb sa fie inaintea muchiei b in vector
{
    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
 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 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();
}