#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("sse,avx,fma,avx2,bmi,bmi2,lzcnt,popcnt")

using namespace std;
using ll = long long;
using ld = long double;

vector<int> repr;

int find(int x) {
  if (repr[x] == x)
    return x;

  return repr[x] = find(repr[x]);
}

void unite(int x, int y) { repr[find(x)] = find(y); }

bool connected(int x, int y) { return find(x) == find(y); }

void solve() {
  int n, m, cost = 0;
  cin >> n >> m;

  vector<tuple<int, int, int>> edges(m);
  for (auto &[w, u, v] : edges) {
    cin >> u >> v >> w;
    --u, --v;
  }

  repr.resize(n);
  for (int i = 0; i < n; ++i)
    repr[i] = i;

  sort(edges.begin(), edges.end());

  vector<pair<int, int>> answer;
  answer.reserve(n - 1);
  for (auto [w, u, v] : edges) {
    if (connected(u, v))
      continue;

    unite(u, v);
    answer.push_back(make_pair(u, v));
    cost += w;
  }

  cout << cost << '\n' << n - 1 << '\n';
  for (auto &[u, v] : answer)
    cout << 1 + u << ' ' << 1 + v << '\n';
}

int main() {
  freopen("apm.in", "r", stdin);
  freopen("apm.out", "w", stdout);
  int t = 1;
  // cin >> t;
  while (t--)
    solve();

  return 0;
}