/* 
 * Laborator 6 - Problema 2
 *
 * Se citesc din fisier urmatoarele date despre un graf simplu ponderat: numarul
 * de varfuri n, numarul de muchii m, muchiile date prin cele doua extremitati 
 * si cost
 * 
 * 1. Modificati algoritmul lui Kruskal pentru a rezolva urmatoarea problema: 
 * data o lista de p < n muchii ale grafului, sa se construiasca (daca se poate)
 * un arbore partial al grafului care contine aceste muchii si are costul minim 
 * - O(mlog(n) + n2) (30p)
 *
 * Ideea solutiei este urmatoarea. Luam Kruskal si ii adaugam din start muchiile
 * date, daca acestea nu fomreaza deja un ciclu. Kruskal ne va da, dintre toti
 * arborii partiali care contin muchiile date, pe cel de cost minim. Ca sa vedem
 * daca 
 *
 */

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pp;

vector <int> store;

int index(int i) {
  if (store.at(i) == i) return i;
  store.at(i) = index(store.at(i));
  return store.at(i);
}

void U(int i, int j) {
  store.at(index(i)) = index(j);
}

int main() {

  ifstream in("apm.in");
  ofstream cout("apm.out");

  int n, m;
  in >> n >> m;

  vector <pair<int, pp > > edges(m);
  vector <pair<int, pp > > spedges;

  store.resize(m, -1);

  for (int i = 0; i < m; ++i) {
    store.at(i) = i;
  }

  for (int i = 0; i < m; ++i) {
    in >> edges.at(i).second.first;
    in >> edges.at(i).second.second;
    in >> edges.at(i).first;

    edges.at(i).second.first -= 1;
    edges.at(i).second.second -= 1;
  }

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

  int res = 0;

  for (int i = 0; i < m; ++i) {
    if (index(edges.at(i).second.first) != index(edges.at(i).second.second)) {
      res += edges.at(i).first;
      U(edges.at(i).second.first, edges.at(i).second.second);
      spedges.push_back(edges.at(i));
    }
  }

  cout << res << "\n";
  cout << n - 1 << "\n";

  for (int i = 0; i < n - 1; ++i) {
    cout << spedges.at(i).second.first + 1 << " ";
    cout << spedges.at(i).second.second + 1 << "\n";
  }

  in.close();

  return 0;
}