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

using namespace std;

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

struct edge {
  int x, y, c;
  edge(int a, int b, int cost) {
    x = a;
    y = b;
    c = cost;
  }
};

bool compare(const edge& a, const edge& b) {
  return a.c < b.c;
}

bool add_edge (const edge& e, unordered_map<int, int>& map) {
  int x_parent = e.x;
  cout<<e.c<<" "<<e.x<<" "<<e.y<<"\n";
  while (map[x_parent] != x_parent) {
    x_parent = map[x_parent];
  }
  int y_parent = e.y;
  while (map[y_parent] != y_parent) {
    y_parent = map[y_parent];
  }
  cout<<"Parent "<<x_parent<<" "<<y_parent<<"\n";
  if (x_parent == y_parent) {
    cout<<"FALSE\n";
    return false;
  }
  map[x_parent] = y_parent;
  // for (int parent : {e.x, e.y}) {
  //   while (map[parent] != parent) {
  //     const auto& aux = parent;
  //     parent = map[parent];
  //     map[aux] = y_parent;
  //   }
  //   map[parent] = y_parent;
  // }
  // int x_parent = map[e.x];
  return true;
}

int main (int argc, char const *argv[]) {
  int n, m;
  in>>n>>m;
  vector<edge> edges;
  for (int i = 0; i < m; ++i) {
    int x, y, c;
    in>>x>>y>>c;
    edges.push_back(edge(x, y, c));
  }
  sort(edges.begin(), edges.end(), compare);
  unordered_map<int, int> subtree_map;
  vector<edge> result;
  for (int i = 1; i <= n; ++i) {
    subtree_map[i] = i;
  }
  int cost = 0;
  for (const auto& edge : edges) {
    if (add_edge(edge, subtree_map)) {
      cost += edge.c;
      result.push_back(edge);
    }
  }
  out<<cost<<"\n";
  out<<result.size()<<"\n";
  for (const auto& e:edges) {
    out<<e.x<<" "<<e.y<<"\n";
  }
  return 0;
}