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

using namespace std;

struct edge {
  int from, to, 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;
  scanf("%d %d", &n, &m);
  vector<edge> nodes[n + 1];

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

    edge e2;
    e2.from = to;
    e2.to = from;
    e2.cost = cost;
    nodes[to].push_back(e2);
  }

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

  int seen = 1;
  int min_cost = 0;

  set<int> treeNodes;
  vector<edge> mstree;
  treeNodes.insert(1);
  vector<edge>::iterator it;
  for (it = nodes[1].begin(); it != nodes[1].end();it++) {
    heap.push(*it);
    //    cout << "Pushed " << it->cost << endl;
  }

  while (seen < n) {
    /*cout << endl;
    cout << "min_cost" << min_cost << endl;
    cout << "Seen " << seen << endl;
    cout << "Heap.top" << heap.top().cost << endl;*/
    edge e = heap.top(); heap.pop();
    if (treeNodes.find(e.to) != treeNodes.end() &&
        treeNodes.find(e.from) != treeNodes.end()) {
      //      cout << "Ignoring"  << endl;
      continue;
    }

    treeNodes.insert(e.to);
    mstree.push_back(e);
    min_cost += e.cost;
    /*    cout << "e.to = " << e.to << endl;
          cout << "e.to.size()" << nodes[e.to].size() << endl;*/
    for (it = nodes[e.to].begin(); it != nodes[e.to].end(); it++) {
      heap.push(*it);
      //      cout << "Adding " << it->cost << endl;
    }
    seen++;
  }

  printf("%d\n", min_cost);
  printf("%d\n", mstree.size());

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

  return 0;
}