#include <cstdio>
#include <vector>
#include <algorithm>
#include <iterator>

using namespace std;

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

const int NMAX = 200005;
int N, M, array_set[NMAX], counter = 1, total_cost;

vector<struct edge *> edges;
vector<struct edge *> total_edges;
vector<int> vector_array[NMAX];

bool less_edge(struct edge *a, struct edge* b) {
  return a->cost < b->cost;
}

void join(int x, int y) {
  if (x > y)
    swap(x, y);
  int aux;

  while(!vector_array[y].empty()) {
    aux = vector_array[y].back();
    array_set[aux] = x;
    vector_array[y].pop_back();
    vector_array[x].push_back(aux);
  }

}

void read() {
  freopen("apm.in", "r", stdin);
  freopen("apm.out", "w", stdout);
  scanf("%d", &N);
  scanf("%d", &M);
  struct edge *new_edge = NULL;
  for(int i = 1; i <= M; i++) {
    new_edge = new struct edge;
    scanf("%d%d%d", &new_edge->x, &new_edge->y, &new_edge->cost);
    edges.push_back(new_edge);
  }

  sort(edges.begin(), edges.end(), &less_edge);
}

void add_edge(int from, int set) {
  array_set[from] = set;
  vector_array[set].push_back(from);
}

void solve() {
  vector<struct edge*>::iterator it;
  struct edge* edge;
  for(it = edges.begin(); it != edges.end(); it++) {
    edge = *it;
    if (array_set[edge->x] == 0) {
      /* Add a the edge between x and y and add it to the total set. Make them
       * both of the same set. */
      if (array_set[edge->y] == 0) {
        add_edge(edge->y, counter);
        counter++;
      }

      add_edge(edge->x, array_set[edge->y]);
      total_cost += edge->cost;
      total_edges.push_back(edge);
    } else if (array_set[edge->y] == 0) {
      /* x is already in a set. add y to it. */
      add_edge(edge->y, array_set[edge->x]);

      total_cost += edge->cost;
      total_edges.push_back(edge);
    } else if (array_set[edge->x] != array_set[edge->y]) {
      /* x and y belong to different sets. Have to join them. */
      join(array_set[edge->x], array_set[edge->y]);
      total_cost += edge->cost;
      total_edges.push_back(edge);
    } else {
      continue;
    }
  }
}

void print() {
  printf("%d\n%lu\n", total_cost, total_edges.size());
  vector<struct edge*>::iterator it;
  for(it = total_edges.begin(); it != total_edges.end(); it++) {
    printf("%d %d\n", (*it)->y, (*it)->x);
  }
}

int main() {
  read();
  solve();
  print();
  return 0;
}