#include <iostream>
#include <algorithm>

#define MAXN 200000
#define MAXM 400000

using namespace std;

struct elem{
  bool used;
  int a, b, cost;
};

bool comp(elem a, elem b) {
  return a.cost < b.cost;
}

int unions[MAXN + 1];
elem edges[MAXM];

int findParent(int x) {
  if ( x == unions[x] )
    return x;
  return unions[x] = findParent(unions[x]);
}

void unite(int a, int b) {
  int parentA, parentB;

  parentA = findParent(a);
  parentB = findParent(b);
  if ( parentA != parentB )
    unions[parentA] = parentB;
}

int main() {
  FILE *fin, *fout;
  fin = fopen("apm.in", "r");
  fout = fopen("apm.out", "w");

  int n, m, i, ans, ct;

  fscanf(fin, "%d%d", &n, &m);

  for ( i = 1; i <= n; i++ ) {
    unions[i] = i;
  }

  for ( i = 0; i < m; i++ ) {
    fscanf(fin, "%d%d%d", &edges[i].a, &edges[i].b, &edges[i].cost);
  }

  sort(edges, edges + m, comp);

  ans = ct = 0;
  for ( i = 0; i < m; i++ ) {
    if ( findParent(edges[i].a) != findParent(edges[i].b) ) {
      edges[i].used = true;
      unite(edges[i].a, edges[i].b);
      ans += edges[i].cost;
      ct++;
    }
  }

  fprintf(fout, "%d\n%d\n", ans, ct);
  for ( i = 0; i < m; i++ )
    if ( edges[i].used )
      fprintf(fout, "%d %d\n", edges[i].a, edges[i].b);

  fclose(fin);
  fclose(fout);

  return 0;
}