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

int main() {
#ifndef LOCAL
  freopen("apm.in", "r", stdin);
  freopen("apm.out", "w", stdout);
#endif
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n, m;
  cin >> n >> m;

  vector<vector<pair<int, int>>> g(n);
  for (; m--;) {
    int u, v, c;
    cin >> u >> v >> c;
    --u;
    --v;
    g[u].emplace_back(c, v);
    g[v].emplace_back(c, u);
  }

  priority_queue<pair<int, int>, vector<pair<int, int>>,
                 greater<pair<int, int>>>
      q;

  vector<int> d(n, INT_MAX);
  vector<int> p(n, -1);
  vector<bool> used(n, false);

  d[0] = 0;
  q.emplace(0, 0);
  long long s = 0;

  while (!q.empty()) {
    auto [c, u] = q.top();
    q.pop();
    if (used[u]) continue;
    used[u] = true;
    s += c;
    for (auto [e, v] : g[u]) {
      if (!used[v] && e < d[v]) {
        d[v] = e;
        p[v] = u;
        q.emplace(d[v], v);
      }
    }
  }

  cout << s << "\n" << n - 1 << "\n";
  for (int u = 1; u < n; ++u) cout << (u + 1) << " " << (p[u] + 1) << "\n";

  return 0;
}