#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

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

const int NMax = 400005;
pair <int, int> P[NMax];
int k;
int N, M, Total, TT[NMax], RG[NMax];

struct Muchie
{
    int x, y, cost;
}V[NMax];

bool Compare(Muchie a, Muchie b)
{
  return a.cost < b.cost;
}

void Read()
{
  in >> N >> M;
  for(int i = 1; i<=M ; i++)
    in >> V[i].x >> V[i].y >> V[i].cost;
  sort(V+1, V+M+1, Compare);
  for(int i = 1; i<=N; i++)
  {
    TT[i] = i;
    RG[i] = 1;
  }
}

int Find(int Nod)
{
  while(TT[Nod] != Nod)
    Nod = TT[Nod];
  return Nod;
}

void Unire(int x, int y)
{
  if(RG[x] < RG[y])
    TT[x] = y;
    else
      TT[y] = x;
  if(RG[x] == RG[y]) RG[x]++;
}

void Rezolva()
{
  for(int i = 1; i<=M; i++)
  {
    int a = Find(V[i].x);
    int b = Find(V[i].y);
    if(a != b)
    {
      Unire(a, b);
      P[++k].first = V[i].x;
      P[k].second = V[i].y;
      Total+=V[i].cost;
    }
  }
}

void Afisare()
{
  out << Total <<"\n";
  out << N-1 << "\n";
  for(int i = 1; i<=k; i++)
    out << P[i].first <<" "<< P[i].second <<"\n";
}

int main()
{
  Read();
  Rezolva();
  Afisare();
}