#include <iostream>
#include <vector>
#include <algorithm>

#define MAXN 200000
#define MAXM 400000

using namespace std;

struct edge{
  int pos, cost;
};

struct node{
  vector <edge> edges;
};

struct edge2{
  int a, b, cost;
};

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

int unions[MAXN + 1];
edge2 edges[MAXM];
int ans[MAXN][2];
int ansSize;

int findUnion(int a) {
  if ( a == unions[a] )
    return a;
  return unions[a] = findUnion(unions[a]);
}

void unite(int a, int b) {
  int unionA, unionB;

  unionA = findUnion(a);
  unionB = findUnion(b);

  if ( unionA != unionB ) {
    unions[unionB] = unionA;
  }
}


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

  int n, m, i, totCost;

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

  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);

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

  ansSize = totCost = 0;
  for ( i = 0; i < m; i++ ) {
    if ( findUnion(edges[i].a) != findUnion(edges[i].b) ) {
      totCost += edges[i].cost;
      unite(edges[i].a, edges[i].b);
      ans[ansSize][0] = edges[i].a;
      ans[ansSize][1] = edges[i].b;
      ansSize++;
    }
  }

  fprintf(fout, "%d\n%d\n", totCost, n - 1);

  for ( i = 0; i < ansSize; i++ ) {
    fprintf(fout, "%d %d\n", ans[i][0], ans[i][1]);
  }

  fclose(fin);
  fclose(fout);

  return 0;
}