#include <fstream>
#include <vector>
#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;

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)
{
     T[x]=y;
}

void Kruskal()
{
     sort(E.begin(),E.end(),cmp());
     for(int i=1;i<=N;++i)T[i]=i;
     for(int i=0;i<M && sol[0]!=N-1;++i)
     {
          int g1=gr(E[i].x),g2=gr(E[i].y);
          if(g1!=g2)
                    cost+=E[i].c , sol[++sol[0]]=i , Reunion(g1,g2);
     }

}

void PrintOutput()
{
     g<<cost<<'\n';
     g<<N-1<<'\n';
     for(int i=1;i<N;++i)g<<E[sol[i]].x<<' '<<E[sol[i]].y<<'\n';
}
int main()
{
     ReadInput();
     Kruskal();
     PrintOutput();
     return 0;
}