#include <bits/stdc++.h>

using namespace std;

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

int n, m, x, y, c, f[400002], L[200002], sol, nr;

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

int main()
{
  fin >> n >> m;
  for (int i = 1; i <= m; i++) {
    fin >> x >> y >> c;
    v.push_back({c, {x, y}});
  }
  for (int i = 1; i <= n; i++)
    L[i] = i;
  sort (v.begin(), v.end());
  for (int i = 0; i < m && nr < n; i++) {
    if (L[v[i].second.first] != L[v[i].second.second]) {
      sol += v[i].first;
      int k = L[v[i].second.second];
      for (int j = 1; j <= n; j++)
        if (L[j] == k) L[j] = L[v[i].second.first];
      nr++;
      rez.push_back({v[i].second.first, v[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;
}