#include <algorithm>
#include <iostream>
#include <fstream>
#include <cassert>
#include <vector>

using namespace std;

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

struct Edge{
  int a;
  int b;
  int c;
};

const int NMAX = 200000;
const int MMAX = 400000;
const int DIM = 1000000;

int n, m, res, poz;
int sef[1 + NMAX];
int ssz[1 + NMAX];
char buff[DIM];
Edge v[1 + MMAX];
vector < Edge > output;

bool cmp(Edge x, Edge y){
  return x.c < y.c;
}

int rread(){
  char sgn = '+';
  int nr = 0;

  while(!isdigit(buff[poz])){
    sgn = buff[poz];
    if(++poz == DIM){
      in.read(buff, DIM);
      poz = 0;
    }
  }

  while(isdigit(buff[poz])){
    nr = nr * 10 + (buff[poz] - '0');
    if(++poz == DIM){
      in.read(buff, DIM);
      poz = 0;
    }
  }

  if(sgn == '-')
    nr *= -1;
  return nr;
}

void read(){
  //in >> n >> m;
  n = rread();
  m = rread();
  for(int i = 1; i <= m; i++){
    //in >> v[i].a >> v[i].b >> v[i].c;
    v[i].a = rread();
    v[i].b = rread();
    v[i].c = rread();
  }
  in.close();
}

int getsef(int el){
  if(sef[el] == el)
    return el;
  else{
    sef[el] = getsef(sef[el]);
    return sef[el];
  }
}

void write(){
  out << res << '\n' << n - 1 << '\n';
  for(int i = 0; i < output.size(); i++)
    out << output[i].a << ' ' << output[i].b << '\n';
  out.close();
}

int main()
{
  read();
  sort(v + 1, v + m + 1, cmp);
  for(int i = 1; i <= n; i++){
    sef[i] = i;
    ssz[i] = 1;
  }

  for(int i = 1; i <= m; i++){
    int bx = getsef(v[i].a);
    int by = getsef(v[i].b);

    if(bx != by){
      assert(bx != by);
      if(ssz[by] <= ssz[bx]){
        ssz[bx] += ssz[by];
        sef[by] = bx;
      }else{
        ssz[by] += ssz[bx];
        sef[bx] = by;
      }
      res += v[i].c;
      output.push_back(v[i]);
    }
  }
  write();
  return 0;
}