#include <cstdio>
#include <algorithm>

using namespace std;
const int MAX_M = 400000;
const int MAX_N  = 200000;

struct Muchie {
  int u;
  int v;
  int cost;
    
  bool operator < (const Muchie &other) const {
    return this->cost < other.cost;
  }
};

Muchie m[5 + MAX_M];
int tata[5 + MAX_N], h[5 + MAX_N];
Muchie sol[5 + MAX_N];

void my_union(int x, int y) {
  if (h[x] > h[y]) {
    h[y] = h[x];
    tata[y] = x;
  }
  else if (h[y] > h[x]) {
    h[x] = h[y];
    tata[x] = y;
  }
  else {
    ++h[x];
    ++h[y];
    tata[y] = x;
  }
}

int my_find(int x) {
  while (tata[x] != x)
    x = tata[x];
  return x;
}

int main() {
  freopen("apm.in", "r", stdin);
  freopen("apm.out", "w", stdout);
    
  int N, M;
  scanf("%d%d", &N, &M);
  for (int i = 1; i <= M; ++i) {
    int u, v, cost;
    scanf("%d%d%d", &u, &v, &cost);
    m[i].u = u;
    m[i].v = v;
    m[i].cost = cost;
  }
  sort(m + 1, m + M + 1);
  for (int i = 1; i <= N; ++i) {
    tata[i] = i;
    h[i] = 1;
  }
  int k = 0, cost = 0;
  for (int i = 1; i <= M; ++i) {
    int n1 = my_find(m[i].u);
    int n2 = my_find(m[i].v);
    if (n1 != n2) {
      cost += m[i].cost;
      my_union(n1, n2);
      sol[++k] = m[i];
    }
  }
  printf("%d\n%d\n", cost, N - 1);
  for (int i = 1; i <= k; ++i) {
    printf("%d %d\n", sol[i].u, sol[i].v);
  }
  return 0;
}