#include <stdio.h>
#include <assert.h>
#include <vector>
#include <queue>
#include <stdlib.h>

using std::vector;
using std::priority_queue;

#define MAX_M 400000
#define MAX_N 200000
#define NIL -1

struct cell {
  int u, v, cost;

  cell() {

  }

  cell(int u, int v, int cost) {
    this -> u = u;
    this -> v = v;
    this -> cost = cost;
  }
} edge[MAX_M + 1];

typedef struct {
  bool operator()(const int &X, const int &Y) {
    return edge[X].cost > edge[Y].cost;
  }
} minHeap;

int N, M;
long long int total;
int* adj[MAX_N + 1];
char seen[MAX_N + 1];
int size[MAX_N + 1];
priority_queue <int, vector <int>, minHeap> heap;

void Prim(int S) {
  int i, u, v, curr, pos;

  seen[0] = 1;
  edge[0] = cell(0, S, 0);
  heap.push(0);
  for (pos = 1; pos <= N; pos++) {
    do {
      curr = heap.top();
      heap.pop();
    } while (!heap.empty() && (seen[edge[curr].v] & seen[edge[curr].u]));

    if (seen[edge[curr].v] ^ seen[edge[curr].u]) {
      if (seen[edge[curr].u] == 1) {
        u = edge[curr].v;
      } else {
        u = edge[curr].u;
      }

      seen[u] = 1;
      total += edge[curr].cost;
      edge[curr].cost = NIL;
      for (i = 0; i < size[u]; i++) {
        if (edge[adj[u][i]].u == u) {
          v = edge[adj[u][i]].v;
        } else {
          v = edge[adj[u][i]].u;
        }
        if (!seen[v]) {
          heap.push(adj[u][i]);
        }
      }
    }
  }
}

int main(void) {
  int i, u, v, cost;
  FILE *f = fopen("apm.in", "r");

  fscanf(f, "%d %d", &N, &M);
  for (i = 1; i <= M; i++) {
    fscanf(f, "%d %d %d", &edge[i].u, &edge[i].v, &edge[i].cost);
    size[edge[i].u]++;
    size[edge[i].v]++;
  }
  fclose(f);

  for (u = 1; u <= N; u++) {
    adj[u] = (int*)calloc(size[u], sizeof(int));
    size[u] = 0;
  }
  for (i = 1; i <= M; i++) {
    adj[edge[i].u][size[edge[i].u]++] = i;
    adj[edge[i].v][size[edge[i].v]++] = i;
  }

  Prim(1);
   // assert(0);
  freopen("apm.out", "w", stdout);
  fprintf(stdout, "%lld\n%d\n", total, N - 1);
  for (i = 1; i <= M; i++) {
    if (edge[i].cost == NIL) {
      fprintf(stdout, "%d %d\n", edge[i].u, edge[i].v);
    }
  }
  fclose(stdout);
  return 0;
}