#include <bits/stdc++.h>
using namespace std;

const int Nmax = 200005;

int n, m;
int h[Nmax], P[Nmax];
vector<pair<int, pair<int, int>>> e;
vector<pair<int, int>> sol;

int root(int x) {
  if (P[x] != x) P[x] = root(P[x]);
  return P[x];
}

void unite(int x, int y) {
  int rx = root(x), ry = root(y);
  if (h[rx] > h[ry]) {
    P[ry] = rx;
    h[rx]++;
  } else {
    P[rx] = ry;
    h[ry]++;
  }
}

int main() {
  ios_base::sync_with_stdio(false);
  ifstream cin("apm.in");
  ofstream cout("apm.out");

  cin >> n >> m;
  int a, b, c;
  while (m--) {
    cin >> a >> b >> c;
    e.push_back({c, {a, b}});
  }
  sort(e.begin(), e.end());

  for (int i = 1; i <= n; ++i) P[i] = i, h[i] = 1;

  int cost = 0;
  for (auto edge : e) {
    if (root(edge.second.first) == root(edge.second.second)) continue;
    cost += edge.first;
    unite(edge.second.first, edge.second.second);
    sol.emplace_back(edge.second.first, edge.second.second);
  }

  cout << cost << "\n";
  cout << sol.size() << "\n";
  for (auto edge : sol) cout << edge.first << " " << edge.second << "\n";
}