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

using namespace std;

const int nmax = 2e5, mmax = 4e5;
int used[5 + mmax], par[5 + nmax], card[5 + nmax];

struct Edge {
  int u, v, cost;
} edge[5 + mmax];

int root(int u) {
  if (par[u] == u)
    return u;
  return par[u] = root(par[u]);
}

bool unite(int u, int v) {
  u = root(u);
  v = root(v);
  if (u == v)
    return false;
  if (card[u] < card[v])
    swap(u, v);
  card[u] += card[v];
  par[v] = u;
  return true;
}

int main() {
  ifstream fin("apm.in");
  ofstream fout("apm.out");
  int n, m;
  fin >> n >> m;
  for (int i = 1; i <= m; i++)
    fin >> edge[i].u >> edge[i].v >> edge[i].cost;
  sort(edge + 1, edge + m + 1, [&](Edge a, Edge b) {
    return a.cost < b.cost;
  });
  for (int i = 1; i <= n; i++) {
    par[i] = i;
    card[i] = 1;
  }
  long long ans = 0;
  for (int i = 1; i <= m; i++)
    if (unite(edge[i].u, edge[i].v)) {
      used[i] = 1;
      ans += edge[i].cost;
    }
  fout << ans << '\n' << n - 1 << '\n';
  for (int i = 1; i <= m; i++)
    if (used[i])
      fout << edge[i].u << ' ' << edge[i].v << '\n';
  return 0;
}