#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

bool cmp(pair<int, pair<int, int>> a, pair<int, pair<int, int>> b) {
  return a.first < b.first;
}

class disjointSet {
  vector<int> parent;
  vector<int> rank;

public:
  disjointSet(int n) : parent(n), rank(n, 0) {
    for (int i = 0; i < n; i++)
      parent[i] = i;
  }
  int find(int x) {
    if (parent[x] != x)
      parent[x] = find(parent[x]);
    return parent[x];
  }
  void unite(int x, int y) {
    int xParent = find(x);
    int yParent = find(y);

    if (rank[xParent] < rank[yParent]) {
      int aux = xParent;
      xParent = yParent;
      yParent = aux;
    }
    
    parent[yParent] = xParent;
    
    if (rank[xParent] == rank[yParent]) {
      rank[xParent]++;
    }
  }
};

class graph {
  int edges;
  int vertices;
  int cost;
  vector<pair<int, pair<int, int>>> weights;

public:
  graph(int n, int m) : vertices(n), edges(m), weights(m), cost(0) {};
  void readEdges(istream& in) {
    int v1, v2, w;
    for (int i = 0; i < edges; i++) {
      in >> v1 >> v2 >> w;
      weights[i] = make_pair(w, make_pair(v1 - 1, v2 - 1));
    }
  }
  graph kruskal() {
    disjointSet S(edges);
    graph result(vertices, 0);
    int v1, v2;
    sort(weights.begin(), weights.end(), cmp);
    for (auto weight : weights) {
      v1 = weight.second.first;
      v2 = weight.second.second;
      if (S.find(v1) != S.find(v2)) {
        S.unite(v1, v2);
        result.weights.push_back(make_pair(weight.first, make_pair(v1, v2)));
        result.edges++;
        result.cost += weight.first;
      }
    }
    return result;
  }
  void print(ostream& out) {
    out << cost << endl;
    out << weights.size() << endl;
    for (auto weight : weights) {
      out << weight.second.second + 1 << ' ' << weight.second.first + 1 << endl;
    }
  }
};

int main() {
  int n, m;
  ifstream in("apm.in");
  ofstream out("apm.out");
  in >> n >> m;
  graph G(n, m);
  G.readEdges(in);
  graph apm = G.kruskal();
  apm.print(out);
  return 0;
}