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

class 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;
  }

  bool operator < (cell &other) {
    return cost() < other.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, total;
int* adj[MAX_N + 1];
int size[MAX_N + 1];
int boss[MAX_N + 1];

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 init() {
  int u;

  for (u = 1; u <= N; u++) {
    boss[u] = u;
  }
}

int find(int u) {
  int tmp, r = u;

  while (r != boss[r]) {
    r = boss[r];
  }
  while (r != u) {
    tmp = boss[u];
    boss[u] = r;
    u = tmp;
  }
  return r;
}

void unify(int u, int v) {
  boss[find(u)] = boss[find(v)];
}


void sort(int begin, int end) {
  int b = begin, e = end;
  cell tmp, pivot = edge[(b + e) >> 1];

  while (b <= e) {
    while (edge[b] < pivot) {
      b++;
    }
    while (pivot < edge[e]) {
      e--;
    }
    if (b <= e) {
      tmp = edge[b];
      edge[b++] = edge[e];
      edge[e--] = tmp;
    }
  }
  if (begin < e) {
    sort(begin, e);
  }
  if (b < end) {
    sort(b, end);
  }
}

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

  init();
  sort(1, M);

  int pos = 0;
  long long int total = 0;
  for (i = 1; i <= M; i++) {
    if (find(edge[i].u()) != find(edge[i].v())) {
      unify(edge[i].u(), edge[i].v());
      edge[++pos] = edge[i];
      total += edge[i].cost();
    }
  }

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