#include <cstring>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <set>
#include <iostream>
#include <queue>

using namespace std;

struct edge {
  int from, to, cost;

  edge(int from, int to, int cost) {
    this->from = from;
    this->to = to;
    this->cost = cost;
  }
};

struct edge_cmp {
  bool operator() (const edge& e1, const edge& e2) {
    return e1.cost > e2.cost;
  }
};

int main() {

  freopen("apm.in", "r", stdin);
  freopen("apm.out", "w", stdout);

  int n, m, from, to, cost;
  scanf("%d %d", &n, &m);
  vector<edge> nodes[n + 1];

  for (int i = 0; i < m; i++) {
    scanf("%d %d %d", &from, &to, &cost);
    edge e(from, to, cost);
    nodes[from].push_back(e);
    edge e2(to, from, cost);
    nodes[to].push_back(e2);
  }

  priority_queue<edge, vector<edge>, edge_cmp> heap;

  vector<edge> mstree;
  vector<edge>::iterator it;
  for (it = nodes[1].begin(); it != nodes[1].end();it++)
    heap.push(*it);

  int n_seen = 1, min_cost = 0;
  int seen[n + 1];
  memset(seen, 0, sizeof(int) * (n + 1));
  seen[1] =  1;

  while (n_seen < n) {
    edge e = heap.top(); heap.pop();
    if (seen[e.to] == 1 && seen[e.from] == 1)
      continue;

    seen[e.to] = 1;
    mstree.push_back(e);
    min_cost += e.cost;

    for (it = nodes[e.to].begin(); it != nodes[e.to].end(); it++)
      if (!seen[it->to])
        heap.push(*it);
    n_seen++;
  }

  printf("%d\n%d\n", min_cost, mstree.size());
  for (it = mstree.begin(); it != mstree.end(); it++)
    printf("%d %d \n", it->from, it->to);
  return 0;
}