#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>
#define Nmax 200099
#define pb push_back
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");

int N,M,T[Nmax],sol[Nmax],cost,R[Nmax];
struct edge{int x,y,c;};

struct cmp
{
     bool operator()(const edge &A,const edge &B)const
     {
          if(A.c<B.c)return 1;
          return 0;
     };
};
vector < edge > E;


void ReadInput()
{
     f>>N>>M; edge muchie;
     for(int i=1;i<=M;++i)
          f>>muchie.x>>muchie.y>>muchie.c , E.pb(muchie);
}

int gr(int x)
{
     if(T[x]!=x)T[x]=gr(T[x]);
     return T[x];
}

void Reunion(int x,int y)
{
     x=gr(x),y=gr(y);
     if(R[x]<R[y])T[x]=y;
          else if(R[x]>R[y])T[y]=x;
               else T[x]=y, R[y]+=R[x];

}


int main()
{
     ReadInput();
     sort(E.begin(),E.end(),cmp());
     for(int i=1;i<=N;++i)T[i]=i,R[i]=1;
     for(int i=0;i<M && sol[0]!=N-1;++i)
          {
               int x=E[i].x,y=E[i].y,c=E[i].c;
               if(gr(x)!=gr(y))
                    cost+=c , sol[++sol[0]]=i , Reunion(x,y);
          }
     g<<cost<<'\n';
     g<<N-1<<'\n';
     for(int i=1;i<=sol[0];++i)g<<E[sol[i]].x<<' '<<E[sol[i]].y<<'\n';
     return 0;
}