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

void swap(long &a,long &b)
{
 long c = a;
 a = b;
 b = c;
}

long N,M;

long HS;
long Heap[200005];
long Pos[200005];
long Distante[200005];
long Parinti[200005];
long Sum;
long Out1[200005];
long Out2[200005];

vector<pair<int,int> *> *Muchii;

void heapify(long n)
{
 long done = 0;
 while (done == 0)
  {
   long sml = n;
   long l = sml << 1;
   long r = l + 1;
   if ((l <= HS) && (Distante[Heap[l]] < Distante[Heap[sml]]))
     {
      sml = l;
     }
   if ((r <= HS) && (Distante[Heap[r]] < Distante[Heap[sml]]))
     {
      sml = r;
     }
   if (sml != n)
     {
      swap(Heap[sml],Heap[n]);
      swap(Pos[Heap[sml]],Pos[Heap[n]]);
      n = sml;
     }
    else
     {
      done = 1;
     }
  }
}

long extrageMin(void)
{
 long res = Heap[1];

 Heap[1] = Heap[HS];
 HS -= 1;

 heapify(1);

 return res;
}

void improvenode(long n)
{
 long p = Pos[n];
 while ((p > 1) && (Distante[Heap[p >> 1]] > Distante[Heap[p]]))
  {
   swap(Heap[p >> 1],Heap[p]);
   swap(Pos[Heap[p >> 1]],Pos[Heap[p]]);
   p >>= 1;
  }
}

int main(void)
{
 long i,a,b,d;
 fstream fin("apm.in",ios::in);
 fstream fout("apm.out",ios::out);
 fin >> N >> M;
 Muchii = new vector<pair<int,int> *>[N + 5];
 for (i = 1;i <= N;i += 1)
  {
   Muchii[i].reserve(20);
  }
 for (i = 0;i < M;i += 1)
  {
   fin >> a >> b >> d;
   Muchii[a].push_back(new pair<int,int>(b,d));
   Muchii[b].push_back(new pair<int,int>(a,d));
  }
 for (i = 1;i <= N;i += 1)
  {
   Heap[i] = i;
   Pos[i] = i;
   Distante[i] = 60000000;
   Parinti[i] = 0;
  }
 HS = N;
 Distante[1] = 0;
 for (i = 1;i <= N;i += 1)
  {
   d = extrageMin();
   if (i != 1)
     {
      Out1[i] = Parinti[d];
      Out2[i] = d;
      Parinti[d] = -1;
      Sum += Distante[d];
     }
   for (a = 0;a < Muchii[d].size();a += 1)
    {
     if (Parinti[Muchii[d][a]->first] == -1)
       {
        continue;
       }
     if (Muchii[d][a]->second < Distante[Muchii[d][a]->first])
       {
        Distante[Muchii[d][a]->first] = Muchii[d][a]->second;
        Parinti[Muchii[d][a]->first] = d;
        improvenode(Muchii[d][a]->first);
       }
    }
  }
 fout << Sum << "\n" << (N - 1) << "\n";
 for (i = 2;i <= N;i += 1)
  {
   fout << Out1[i] << " " << Out2[i] << "\n";
  }
 fin.close();
 fout.close();
 return 0;
}