#include <fstream>
#include <vector>
#include <string>
#include <algorithm>
#include <tuple>

using namespace std;

const string IN_FILE = "apm.in";
const string OUT_FILE = "apm.out";
const int NIL = -1;

typedef tuple<int, int, int> Edge;

class DisjointSets {
  public:
    DisjointSets(const int _size) :
      size(_size),
      father(vector<int>(_size, NIL)) {}

    int find(const int x) {
        if (father[x] == NIL) {
            return x;
        } else {
            return father[x] = find(father[x]);
        }
    }

    bool merge(const int x, const int y) {
        const int rx = find(x);
        const int ry = find(y);
        if (rx == ry) {
            return false;
        }
        father[rx] = ry;
        return true;
    }

  private:
    int size;
    vector<int> father;
};

vector<Edge> kruskal(const int size, vector<Edge> edges) {
    sort(edges.begin(), edges.end());
    auto sets = DisjointSets(size);
    auto mst = vector<Edge>();
    for (const auto& e : edges) {
        int v, w, c;
        tie(c, v, w) = e;
        if (sets.merge(v, w)) {
            mst.push_back(e);
        }
    }
    return mst;
}

int getCost(const vector<Edge>& edges) {
    int cost = 0;
    for (const auto& e : edges) {
        int v, w, c;
        tie(c, v, w) = e;
        cost += c;
    }
    return cost;
}

int main() {
    ifstream in(IN_FILE);
    int size, edgeCount;
    in >> size >> edgeCount;
    auto edges = vector<Edge>(edgeCount);
    for (int i = 0; i < edgeCount; i++) {
        int v, w, c;
        in >> v >> w >> c;
        --v;
        --w;
        edges[i] = tie(c, v, w);
    }
    in.close();

    const auto mst = kruskal(size, edges);

    ofstream out(OUT_FILE);
    out << getCost(mst) << "\n" << int(mst.size()) << "\n";
    for (const auto& e : mst) {
        int v, w, c;
        tie (c, v, w) = e;
        out << v + 1 << " " << w + 1 << "\n";
    }
    out.close();
    return 0;
}