#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],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 > Edges;
vector < int > sol;


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

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

void Reunion(int x,int y)
{
     T[gr(x)]=gr(y);
}


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