#include <bits/stdc++.h>
#define L 400005
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");

struct EDGE {
  int a, b, c;
};

int n, m;
EDGE edges[L];
vector <EDGE> apm;
vector <pair <int, int>> dsu;

bool cmp(const EDGE &a, const EDGE &b) {
  return a.c < b.c;
}

void initDSU() {
  dsu.resize(n + 1);
  for (int i = 1; i <= n; i++)
    dsu[i] = {i, 1};
}

int getRoot(int x) {
  if (dsu[x].first == x)
    return x;
  dsu[x].first = getRoot(dsu[x].first);
  return dsu[x].first;
}

bool joinDSU(int x, int y) {
  x = getRoot(x);
  y = getRoot(y);

  if (x == y)
    return false;

  if (dsu[x].second < dsu[y].second)
    swap(x, y);

  dsu[y].first = x;
  dsu[x].second += dsu[y].second;

  return true;
}

int main() {
  fin >> n >> m;
  for (int i = 1; i <= m; i++) {
    fin >> edges[i].a >> edges[i].b >> edges[i].c;
  }

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

  initDSU();
  int s = 0;
  for (auto edge : edges) {
    if (joinDSU(edge.a, edge.b)) {
      apm.push_back(edge);
      s += edge.c;
    }
  }

  fout << s << "\n" << n - 1 << "\n";
  for (auto it : apm)
    fout << it.a << " " << it.b << "\n";
  return 0;
}