#include <bits/stdc++.h>

using namespace std;

ifstream fin ("apm.in");
ofstream fout ("apm.out");

int n, m, x, y, c, sol, nr;

struct tree {
  short p;
  short rank;
} v[1027];

void init () {
  for (int i = 1; i <= n; i++) {
    v[i].p = i;
    v[i].rank = 1;
  }
}

int find (int x) {
  if (v[x].p != x)
    find(v[x].p);
  else
    return x;
}

bool Union (int x, int y) {
  int Xroot = find(x);
  int Yroot = find(y);
  if (Xroot != Yroot) {
    if (v[Xroot].rank < v[Yroot].rank)
      v[Xroot].p = Yroot;
    else if (v[Yroot].rank < v[Xroot].rank)
      v[Yroot].p = Xroot;
    else {
      v[Xroot].p = Yroot;
      v[Yroot].rank++;
    }
    return 1;
  }
  return 0;
}


vector<pair<int, int> >rez;
vector<pair<int, pair<int, int> > >a;

int main()
{
  fin >> n >> m;
  for (int i = 1; i <= m; i++) {
    fin >> x >> y >> c;
    a.push_back({c, {x, y}});
  }
  init();
  sort (a.begin(), a.end());
  for (int i = 0; i < m && nr < n; i++) {
    bool ok = Union(a[i].second.first, a[i].second.second);
    if (ok) {
      sol += a[i].first;
      rez.push_back({a[i].second.first, a[i].second.second});
    }
  }
  fout << sol << "\n";
  fout << rez.size() << "\n";
  for (int i = 0; i < rez.size(); i++)
    fout << rez[i].first << " " << rez[i].second << "\n";
  return 0;
}