// Kruskal - O(MlogM+Mlog*N)
#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;}aux;
struct cmp
{
     bool operator()(const edge &A,const edge &B)const
     {
          if(A.c<B.c)return 1;
          return 0;
     }
};
vector < edge > 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);
}

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)
          if(gr(E[i].x)!=gr(E[i].y))
                    cost+=E[i].c , sol[++sol[0]]=i , Reunion(E[i].x,E[i].y);
}

int main()
{
     f>>N>>M;
     for(int i=1;i<=M;++i)
          f>>aux.x>>aux.y>>aux.c , E.pb(aux);
     Kruskal();
     g<<cost<<'\n';
     g<<sol[0]<<'\n';
     for(int i=1;i<=sol[0];++i)g<<E[sol[i]].x<<' '<<E[sol[i]].y<<'\n';
     f.close();g.close();
     return 0;
}