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

using namespace std;

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

int n, m, sol;

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

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

int const nmax = 200000;
int const mmax = 400000;

Edge v[1 + mmax];
vector<Edge> output;
int mark[1 + nmax];
vector<int> mult[1 + nmax];

void reunion(int a, int b) {
  if(mult[b].size() < mult[a].size() ) {
    for(int i=0; i<mult[b].size(); i++) {
      mult[a].push_back(mult[b][i]);
      mark[mult[b][i]] = a;
    }
    mult[b].clear();
  } else {
    for(int i=0; i<mult[a].size(); i++) {
      mult[b].push_back(mult[a][i]);
      mark[mult[a][i]] = b;
    }
    mult[a].clear();
  }
}

int main() {
  in >> n >> m;
  for(int i = 1; i <= m; i++)
    in >> v[i].a >> v[i].b >> v[i].c;
  in.close();

  sort(v + 1, v + m + 1, cmp);

  for(int i = 1; i <= n; i++){
    mark[i] = i;
    mult[i].push_back(i);
  }
  for(int i = 1; i <= m; i++){
    if(mark[v[i].a] != mark[v[i].b]){
      reunion(mark[v[i].a], mark[v[i].b]); //mare atentie!!!
      sol += v[i].c;
      output.push_back(v[i]);
    }
  }

  out << sol<<endl<<(n-1)<<endl;

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