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

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

#define MAX_M 400000
#define MAX_N 200000
#define OFFSET 1000
#define NIL OFFSET + 7

long long int tmp;

struct cell {
private:
  long long int set = 0;

public:
  cell() {

  }

  cell(long long int u, long long int v, long long int cost) {
    this -> set |= u;
    this -> set |= v << 18LL;
    this -> set |= (cost + OFFSET) << 36LL;
  }

  int u() {
    return set & 262143;
  }

  int v() {
    return (set >> 18LL) & 262143;
  }

  int cost() {
    return ((set >> 36LL) & 32767) - OFFSET;
  }
} 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, total;
int* adj[MAX_N + 1];
char seen[MAX_N + 1];
int size[MAX_N + 1];
priority_queue <int, vector <int>, minHeap> heap;

const int sign[2] = {1, -1};

#define MAX_BUFF 65536
char buff[MAX_BUFF];
int ptr = MAX_BUFF;
int d[10], count;

char getChar(FILE *f) {
  if (ptr == MAX_BUFF) {
    fread(buff, 1, MAX_BUFF, f);
    ptr = 0;
  }
  return buff[ptr++];
}

int freef(FILE *f) {
  int result = 0;
  char c, last;

  do {
    last = c;
    c = getChar(f);
  } while (!isdigit(c));
  do {
    result = (result << 3) + (result << 1) + c - '0';
    c = getChar(f);
  } while (isdigit(c));
  return result * sign[last == '-'];
}

void flush() {
  fwrite(buff, 1, ptr, stdout);
}

void putChar(char c) {
  if (ptr == MAX_BUFF) {
    fwrite(buff, 1, MAX_BUFF, stdout);
    ptr = 0;
  }
  buff[ptr++] = c;
}

void put(int v, char c) {
  count = 0;
  int q;

  if (v == 0) {
    d[count++] = 0;
  } else while (v) {
    q = v / 10;
    d[count++] = v - (q << 3) - (q << 1);
    v = q;
  }
  for (q = count - 1; q >= 0; q--) {
    putChar(d[q] + '0');
  }
  putChar(c);
}

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] = cell(edge[curr].u(), edge[curr].v(), 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");

  N = freef(f);
  M = freef(f);
  for (i = 1; i <= M; i++) {
    u = freef(f);
    v = freef(f);
    cost = freef(f);
    edge[i] = cell(u, v, cost);
    size[u]++;
    size[v]++;
  }
  fclose(f);

  //assert(0);

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

  freopen("apm.out", "w", stdout);
  ptr = 0;
  if (total < 0) {
    total = -total;
    putChar('-');
  }
  put(total, '\n');
  put(N - 1, '\n');
  for (i = 1; i <= M; i++) {
    if (edge[i].cost() == NIL) {
      put(edge[i].u(), ' ');
      put(edge[i].v(), '\n');
    }
  }
  flush();
  fclose(stdout);
  return 0;
}