#include <bits/stdc++.h>

using namespace std;

const int nmax = 200010;
const int mmax = 400010;
const int costMax = 1005;

vector < pair <int, int> > apm;
set <pair <int, pair <int, int> > > muchii;

ifstream f("apm.in");
ofstream g("apm.out");

int N, M;

int t[nmax];

int src(int x)
{
  if (x == t[x]) return x;
  src(t[x]);
}

void uneste(int x, int tt)
{
  if (x == t[x]) {
    t[x] = tt;
    return;
  } else {
  int y = t[x];
  t[x] = tt;
  uneste(y, tt);
}
}


int main()
{
  f >> N >> M;
  for (int i = 0; i < M; i++) {
    int x, y, c;
    f >> x >> y >> c;
    muchii.insert(make_pair(c, make_pair(x, y)));
  }

  for (int i = 1; i <= N; i++) {
    t[i] = i;
  }

  int cost = 0;

  for (int i = 1; i < N; i++) {
    int ok = 0;
    pair <int, pair<int, int> > p;
    while (ok == 0) {
      p = *muchii.begin();
      muchii.erase(p);
      if (src(p.second.first) != src(p.second.second)) {
        ok = 1;
      }
    }
    cost += p.first;
    apm.push_back(make_pair(p.second.first, p.second.second));
    uneste(p.second.second, t[p.second.first]);
  }

  g << cost << "\n" << N - 1 << "\n";
  for (auto it : apm) {
    g << it.first << " " << it.second << "\n";
  }
  return 0;
}