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

const int nmax = 2 * 1e5;
const int mmax = 4 * 1e5;

int parent[nmax + 10];
struct edges{
  int u, v, c;

  inline bool operator < (const edges &lol)const{
    return c < lol.c;
  }
}read;
vector <edges> ad;
vector <edges> sol;

static inline int root (int vertex){
  int n0 = vertex;
  while (parent[n0])
    n0 = parent[n0];

  int cur;
  while (parent[vertex]){
    cur = vertex;
    vertex = parent[vertex];
    parent[cur] = n0;
  }
  return n0;
}

static inline void join (const int &x, const int &y){
  int rx = root (x);
  int ry = root (y);
  if (rx != ry){
    parent[rx] = ry;
  }
}

static inline bool query (const int &x, const int &y){
  int rx = root (x);
  int ry = root (y);

  return rx == ry;
}
int main(){

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

  int n, m, cost = 0;
  fin >> n >> m;
  for (int i = 1; i <= m; i++){
    fin >> read.u >> read.v >> read.c;
    ad.push_back(read);
  }

  sort (ad.begin(), ad.end());

  for (int i = 0; i < m; i++){
    if (!query(ad[i].u, ad[i].v)){
      join (ad[i].u, ad[i].v);
      cost += ad[i].c;
      sol.push_back (ad[i]);
    }
  }

  int _size = sol.size();
  fout << cost << "\n" << _size << "\n";
  for (auto cuz: sol){
    fout << cuz.v << " " << cuz.u << "\n";
  }
  return 0;
}