// Kruskal - O(MlogM+Mlog*N)
#include <fstream>
#include <vector>
#include <algorithm>
#define Nmax 200099
#define pb push_back
#include <tuple>
using namespace std;

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

// get<0>(e) => cost
// get<1>(e) => x
// get<2>(e) => y
typedef tuple<int, int, int> edge;
struct cmp{
  bool operator()(edge A, edge B) {
    return get<0>(A) < get<0>(B);
  }
};

int n, m, root[Nmax], cost;
vector < edge > E;
vector < int > sol;

int getroot(int x) {
  if(root[x] != x) {
    root[x] = getroot(root[x]);
  }
  return root[x];
}

void reunion(int x, int y) {
  root[getroot(x)] = getroot(y);
}

void Kruskal() {
  cmp comparator;
  sort(E.begin(), E.end(), comparator);

  for(int i = 1; i <= n; ++i) root[i] = i;

  int i = 0;
  for(auto e : E) {
    int x = get<1>(e), y = get<2>(e);
    int c = get<0>(e);

    if(getroot(x) != getroot(y)) {
      cost += c;
      sol.push_back(i);
      reunion(x, y);
    }
    i++;
  }

}

int main()
{
   f >> n >> m;

   for(int i = 1; i <= m; ++i) {
      int x, y, c;
      f >> x >> y >> c;
      E.push_back(edge(c, x, y));
    }

   Kruskal();

   g<< cost << '\n';
   g<< sol.size() << '\n';
   for (auto i : sol) {
      g<< get<1>(E[i]) << ' ' << get<2>(E[i]) << '\n';
   }

   f.close();g.close();
   return 0;
}