#include <stdio.h>
#include <algorithm>

#define D 0
#define MAXN 200000
#define MAXM 400000

struct edge{
  int u, v;
  int cost;
  int chosen;
};

struct disjointedSetsForest{
  int leader[MAXN+1];

  void init(){
    for(int i = 1; i <= MAXN; i++)
      leader[i] = i;
  }

  int find(int p){
    return leader[p] == p ? p : find(leader[p]);
  }

  void unify(int u, int p){
    leader[find(u)] = find(p);
  }

  int areConnected(int u, int p){
    return find(u) == find(p) ? 1 : 0;
  }
};

struct edge edges[MAXM];
disjointedSetsForest connectedNodes;

static inline void addEdge(int u, int v, int cost, int pos){
  edges[pos].u = u;
  edges[pos].v = v;
  edges[pos].cost = cost;
}

int main(){
  FILE *in, *out;
  int n, m, i, a, b, cost, connected;

  in = fopen("apm.in", "r");
  fscanf(in, "%d%d", &n, &m);
  for(i = 0; i < m; i++){
    fscanf(in, "%d%d%d", &a, &b, &cost);
    addEdge(a, b, cost, i);
  }
  fclose(in);

  std::sort(edges, edges + m, [](struct edge a, struct edge b){return  a.cost < b.cost;});

  if(D)
    for(i = 0; i < m; i++)
      printf("%d: %d %d %d\n", i, edges[i].u, edges[i].v, edges[i].cost);
    

  connectedNodes.init();
  cost = connected = 0;
  for(i = 0; i < m; i++){
    if(connectedNodes.areConnected(edges[i].u, edges[i].v) == 0){
      connectedNodes.unify(edges[i].u, edges[i].v);

      edges[i].chosen = 1;
      cost += edges[i].cost;
      connected++;
    }
  }

  out = fopen("apm.out", "w");
  fprintf(out, "%d\n%d\n", cost, connected);
  for(i = 0; i < m; i++)
    if(edges[i].chosen == 1)
      fprintf(out, "%d %d\n", edges[i].u, edges[i].v);
  fclose(out);

  return 0;
}