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

using namespace std;

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

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

bool compareEdge(Edge a, Edge b) {
  return (a.cost < b.cost);
}

int const NMAX = 2e5;
Edge prim[1 + NMAX];
int root[1 + NMAX];
int treeSize[1 + NMAX];

int findRoot(int node) {
  if(node == root[node]) {
    return node;
  }
  root[node] = findRoot(root[node]);
  return root[node];
}

void connectNode(int a, int b) {
  int rootA = findRoot(a), rootB = findRoot(b);
  if(rootA != rootB) {
    if(treeSize[rootA] < treeSize[rootB]) {
      treeSize[rootB] += treeSize[rootA];
      root[rootA] = rootB;
    }else {
      treeSize[rootA] += treeSize[rootB];
      root[rootB] = rootA;
    }
  }
}

int main() {

  int n, m;
  in >> n >> m;
  for(int i = 1;i <= n;i++) {
    root[i] = i;
    treeSize[i] = 1;
  }
  for(int i = 1;i <= m;i++) {
    int a, b, cost;
    in >> a >> b >> cost;
    prim[i] = {a, b, cost};
  }
  sort(prim+1, prim+m+1, compareEdge);
  int ans = 0;
  vector <Edge> sol;
  for(int i = 1;i <= m;i++) {
    if(findRoot(prim[i].a) != findRoot(prim[i].b)) {
      ans += prim[i].cost;
      sol.push_back(prim[i]);
      connectNode(prim[i].a, prim[i].b);
    }
  }
  out << ans << '\n' << sol.size() << '\n';
  for(int i = 0;i < sol.size();i++) {
    out << sol[i].a << ' ' << sol[i].b << '\n';
  }
  return 0;
}