#include <stdio.h>

const int MAX_NODES = 100'000;
const int MAX_EDGES = 200'000;
const int MAX_COST = 2'000;
const int COST_OFFSET = 1'000;

struct edge {
  int u, v;
};

struct cell {
  edge e;
  int next;
};

cell cells[MAX_EDGES + 1];
edge mst[MAX_NODES];
int edges[MAX_COST + 1];
int ds_parent[MAX_NODES + 1];
int num_nodes, mst_size, mst_cost;

void ds_init() {
  for (int u = 1; u <= num_nodes; u++) {
    ds_parent[u] = u;
  }
}

int ds_find(int u) {
  return (ds_parent[u] == u)
    ? u
    : (ds_parent[u] = ds_find(ds_parent[u]));
}

void ds_union(int u, int v) {
  ds_parent[ds_find(v)] = ds_find(u);
}

void read_data() {
  int num_edges;
  FILE* f = fopen("apm.in", "r");

  fscanf(f, "%d %d", &num_nodes, &num_edges);
  for (int i = 1; i <= num_edges; i++) {
    cell& c = cells[i];
    int cost;
    fscanf(f, "%d %d %d", &c.e.u, &c.e.v, &cost);
    cost += COST_OFFSET;
    c.next = edges[cost];
    edges[cost] = i;
  }

  fclose(f);
}

void consider_edge(int u, int v, int cost) {
  if (ds_find(u) != ds_find(v)) {
    mst[mst_size++] = { u, v };
    mst_cost += cost - COST_OFFSET;
    ds_union(u, v);
  }
}

void kruskal() {
  ds_init();

  for (int cost = 0; cost <= MAX_COST; cost++) {
    for (int p = edges[cost]; p; p = cells[p].next) {
      consider_edge(cells[p].e.u, cells[p].e.v, cost);
    }
  }
}

void write_mst() {
  FILE* f = fopen("apm.out", "w");

  fprintf(f, "%d\n%d\n", mst_cost, num_nodes - 1);
  for (int i = 0; i < num_nodes - 1; i++) {
    fprintf(f, "%d %d\n", mst[i].u, mst[i].v);
  }

  fclose(f);
}

int main() {

  read_data();
  kruskal();
  write_mst();

  return 0;
}