#include <iostream>
#include<fstream>
#include<string.h>
#include<bits/stdc++.h>
#include<math.h>
using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

#define NMAX 100005


int n,m;

struct muchie
{
   int x,y,c;
};

vector <muchie> v,ar;
int r[NMAX],t[NMAX];

int find(int x)
{
   int rad = x;
   while(t[rad]!=0)
   {
      rad = t[rad];
   }

   while(t[x]!=0)
   {
      int y = t[x];
      t[x] = rad;
      x = y;
   }

   return rad;
}

void uneste(int rad1,int rad2)
{
   if(r[rad1] < r[rad2])
   {
      t[rad1] = rad2;
   }
   else if(r[rad1] > r[rad2])
   {
      t[rad2] = rad1;
   }
   else
   {
      t[rad1] = rad2;
      r[rad1]++;
   }
}

bool compara(muchie x,muchie y)
{
   return x.c < y.c;
}

void citeste()
{
   fin>>n>>m;
   for(int i=1;i<=m;i++)
   {
      int x,y,c;
      fin>>x>>y>>c;
      muchie m;
      m.x = x;
      m.y = y;
      m.c = c;
      v.push_back(m);
   }

}

int cost = 0;

int main(){


   citeste();
   sort(v.begin(),v.end(),compara);

   //for(int i=0;i<v.size();i++)
      //cout<<v[i].x<<" "<<v[i].y<<endl;

   //cout<<endl;

   int j=0;
   int i=1;
   while(i<=n-1 && j<m)
   {

      int x = find(v[j].x);
      int y = find(v[j].y);

      if(x!=y)
      {
         i++;
         cost+=v[j].c;
         ar.push_back(v[j]);
         uneste(x,y);
      }
      j++;
   }

   fout<<cost;
   fout<<'\n';
   fout<<n-1<<'\n';
   for(int i=0;i<n-1;i++)
      fout<<ar[i].x<<" "<<ar[i].y<<'\n';;

   return 0;
}