#include <bits/stdc++.h>

using namespace std;

const int maxN = 2e5 + 5, maxM = 4e5 + 5;

struct edge{
  int x, y, value;
  bool operator < (const edge &aux) const{
    return (this->value < aux.value);
  }
}e[maxM];

int f[maxN];
bool chosen[maxM];

int father(int x){
  if (x == f[x])
    return x;
  return f[x] = father(f[x]);
}

void join(int x, int y){
  int fx = father(x), fy = father(y);
  f[fx] = fy;
}

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++)
    scanf("%d %d %d", &e[i].x, &e[i].y, &e[i].value);

  sort(e + 1, e + M + 1);

  for (int i = 1; i <= N; i++)
    f[i] = i;

  int nrE = 0, answer = 0;
  for (int i = 1; i <= M && nrE < N - 1; i++){
    if (father(e[i].x) != father(e[i].y)){
      chosen[i] = true;
      nrE++;
      answer += e[i].value;
      join(e[i].x, e[i].y);
    }
  }

  printf("%d\n%d\n", answer, nrE);
  for (int i = 1; i <= M; i++)
    if (chosen[i])
      printf("%d %d\n", e[i].x, e[i].y);

  return 0;
}