#include <stdio.h>
#include <algorithm>
using namespace std;

struct Edge {
  int x, y, cost;
};

bool cmpEdge(const Edge& e1, const Edge& e2) {
  return e1.cost < e2.cost;
}

#define MAX_N 200000
#define MAX_M 400000

int noNodes, noEdges;
Edge edges[MAX_M];

int setIndex[MAX_N];

int noTreeEdges, treeCost;
int treeEdges[MAX_M];

void init(int n) {
  int i;

  for (i = 0; i < n; ++i)
    setIndex[i] = i;
}

int find(int x) {
  if (setIndex[x] == x)
    return x;
  return setIndex[x] = find(setIndex[x]);
}

void unite(int x, int y) {
  int setX, setY;

  setX = find(x);
  setY = find(y);
  if (setX != setY) {
    if (rand() & 1)
      setIndex[setX] = setY;
    else
      setIndex[setY] = setX;
  }
}

int main() {
  FILE *fin, *fout;
  fin = fopen("apm.in", "r");
  fout = fopen("apm.out", "w");

  int i;
  fscanf(fin, "%d%d", &noNodes, &noEdges);
  for (i = 0; i < noEdges; ++i) {
    fscanf(fin, "%d%d%d", &edges[i].x, &edges[i].y, &edges[i].cost);
    --edges[i].x, --edges[i].y;
  }

  sort(edges, edges + noEdges, cmpEdge);

  init(noNodes);

  noTreeEdges = treeCost = 0;
  for (i = 0; i < noEdges; ++i)
    if (find(edges[i].x) != find(edges[i].y)) {
      unite(edges[i].x, edges[i].y);

      treeEdges[noTreeEdges++] = i;
      treeCost += edges[i].cost;
    }

  fprintf(fout, "%d\n%d\n", treeCost, noTreeEdges);
  for (i = 0; i < noTreeEdges; ++i)
    fprintf(fout, "%d %d\n", edges[treeEdges[i]].x + 1, edges[treeEdges[i]].y + 1);

  fclose(fin);
  fclose(fout);
  return 0;
}