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

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

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

int n,m;

struct disjointedSetsForest{
  int leader[MAXN+1];

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

  int find(int p){
    return leader[p] == p ? p : (leader[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;

int main(){
  FILE *in, *out;
  int i, cost;

  in = fopen("apm.in", "r");
  fscanf(in, "%d%d", &n, &m);
  for(i = 0; i < m; i++){
    fscanf(in, "%d%d%d", &edges[i].u, &edges[i].v, &edges[i].cost);
  }
  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 = 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;
    }
  }

  out = fopen("apm.out", "w");
  fprintf(out, "%d\n%d\n", cost, n-1);
  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;
}