#include <bits/stdc++.h>

const int MAX_N = 2e5;
const int MAX_M = 4e5;

class Edge {
  public:
    int a;
    int b;
    int c;

    bool operator<(Edge y) {
      return c < y.c;
    }
};

Edge edges[MAX_M];

struct UF_Node {
  int head = -1;
  int siz = 1;
};
UF_Node UF[MAX_N];

int root(int pos) {
  return (UF[pos].head == -1) ? pos : UF[pos].head = root(UF[pos].head);
}

void unite(int pos1, int pos2) {
  pos1 = root(pos1);
  pos2 = root(pos2);

  if (UF[pos2].siz < UF[pos1].siz)
    std::swap(pos1, pos2);

  UF[pos1].head = pos2;
  UF[pos2].siz += UF[pos1].siz;
}

bool check(int pos1, int pos2) {
  return root(pos1) == root(pos2);
}

int res[MAX_N];

int main() {
  FILE *fin, *fout;
  int n, m;
  int a, b, c;
  int i, j, ind;
  int sum;

  fin = fopen("apm.in", "r");

  fscanf(fin, "%d%d", &n, &m);
  for (i = 0; i < m; i++) {
    fscanf(fin, "%d%d%d", &a, &b, &c);
    edges[i].a = a;
    edges[i].b = b;
    edges[i].c = c;
  }

  fclose(fin);

  std::sort(edges, edges + m);

  i = 0;
  j = 0;
  ind = 0;
  sum = 0;
  while (j < n) {
    if (UF[edges[i].a].head == -1 && UF[edges[b].a].head == -1) {
      unite(edges[i].a, edges[i].b);
      sum = sum + edges[i].c;
      res[ind++] = i;
      j = j + 2;
    } else if (!check(edges[i].a, edges[i].b) && (UF[edges[i].a].head == -1 || UF[edges[i].b].head == -1)) {
      unite(edges[i].a, edges[i].b);
      sum = sum + edges[i].c;
      res[ind++] = i;
      j = j + 1;
    } else if (!check(edges[i].a, edges[i].b)) {
      unite(edges[i].a, edges[i].b);
      sum = sum + edges[i].c;
      res[ind++] = i;
    }
    i++;
  }

  fout = fopen("apm.out", "w");

  fprintf(fout, "%d\n", sum);
  fprintf(fout, "%d\n", n - 1);
  for (i = 0; i < n - 1; i++)
    fprintf(fout, "%d %d\n", edges[res[i]].a, edges[res[i]].b);

  fclose(fout);

  return 0;
}