#include <fstream>
#include <vector>
using namespace std;

#define nmax 200010
#define inf 1001

struct trio { int a,b,c; };

vector<trio> v;
int dad[nmax], rang[nmax];

void qs(int li, int ls)
{
     int i=li, j=ls;
     int piv = v[(li+ls)/2].c;
     while(i<j)
     {
         while(v[i].c<piv) i++;
         while(v[j].c>piv) j--;
         if(i<=j)
         { 
              swap(v[i],v[j]); 
              i++; 
              j--; 
         }
     }
     if(li<j) qs(li,j);
     if(ls>i) qs(i,ls);
}

int radacina(int nod)
{
   int rad, aux;
   for(rad=nod; rad!=dad[rad]; rad=dad[rad]);
   for(;nod!=dad[nod];)
   {
       aux = dad[nod];
       dad[nod] = rad;
       nod = aux;
   }
   return rad;
}

void reuniune(int a, int b)
{
   if(rang[a]>rang[b]) dad[b] = a; else dad[a] = b;
   if(rang[a]==rang[b]) rang[b]++;
}


int main()
{
    ifstream f("apm.in");
    ofstream g("apm.out");
   
    int N, M;
    int a, b, c;
    int i;
   
    f>>N>>M;
    trio t;
    for(i=1; i<=N; i++)
    { 
         dad[i] = i; 
         rang[i] = 1; 
    }
    for(i=0; i<M; i++)
    {
         f>>t.a>>t.b>>t.c;
         v.push_back(t);
    }
    qs(0,M-1);
   
    int ind = 0;
    long long cost = 0;
   
    for(i=1; i<N; i++)
    {
         while( radacina(v[ind].a) == radacina(v[ind].b) ) ind++;
         cost += v[ind].c;
         v[ind].c = inf;
         reuniune( radacina(v[ind].a), radacina(v[ind].b) );
         ind++;
    }
   
    g<<cost<<"\n"<<N-1<<"\n";
   
    for(ind=1,i=0; ind<N; i++)
         if(v[i].c == inf)
         {
              g<<v[i].a<<" "<<v[i].b<<"\n";
              ind++;
         }
   
   
    return 0;
}