#include <bits/stdc++.h>

using namespace std;

int tata[200005];
int h[200005];

int Find(int x) {
  if (tata[x] == 0) {
    return x;
  }
  return Find(tata[x]);
}

void Union(int x, int y) {
  if (h[Find(x)] < h[Find(y)]) {
    tata[Find(x)] = Find(y);
    return;
  }
  tata[Find(y)] = Find(x);
  if (h[Find(x)] == h[Find(y)]) {
    ++h[Find(x)];
  }
}

int main() {
  freopen("apm.in", "r", stdin);
  freopen("apm.out", "w", stdout);
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);

  int n, m;
  cin >> n >> m;
  int cost_total = 0;
  vector<pair<int, pair<int, int>>> muchii;
  vector<pair<int, int>> apcm;
  for (int i = 1; i <= m; ++i) {
    int x, y, c;
    cin >> x >> y >> c;
    muchii.push_back({c, {x, y}});
  }

  sort(muchii.begin(), muchii.end());
  for (auto muchie : muchii) {
    int cost = muchie.first;
    int x = muchie.second.first;
    int y = muchie.second.second;
    if (Find(x) != Find(y)) {
      Union(x, y);
      apcm.push_back({x, y});
      cost_total += cost;
      if (apcm.size() == n) {
        break;
      }
    }
  }
  cout << cost_total << '\n';
  cout << apcm.size() << '\n';
  for (auto pii : apcm) {
    cout << pii.first << ' ' << pii.second << '\n';
  }
  return 0;
}