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

using namespace std;

class DisjointSets {
  public:
    static const int NIL = -1;

    DisjointSets(const int size = 0):
      father(vector<int>(size, NIL)),
      rank(vector<int>(size, 0)) {}

    int Size() const {
        return int(father.size());
    }

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

    bool Merge(int x, int y) {
        x = Find(x);
        y = Find(y);
        if (x == y)
            return false;
        if (rank[x] < rank[y])
            swap(x, y);
        father[y] = x;
        rank[x] = max(rank[x], rank[y] + 1);
        return true;
    }

  private:
    vector<int> father, rank;
};

class Edge {
  public:
    Edge(const int _from, const int _to, const int _cost):
      from(_from),
      to(_to),
      cost(_cost) {}

    int From() const {
        return from;
    }

    int To() const {
        return to;
    }

    int Cost() const {
        return cost;
    }

    bool operator<(const Edge &other) const {
        if (cost != other.cost)
            return cost < other.cost;
        if (from != other.from)
            return from < other.from;
        return to < other.to;
    }

  private:
    int from, to, cost;
};

vector<Edge> Kruskal(const int v, vector<Edge> &edges) {
    sort(edges.begin(), edges.end());
    DisjointSets forest = DisjointSets(v);
    vector<Edge> mst;
    for (int i = 0; i < int(edges.size()); ++i)
        if (forest.Merge(edges[i].From(), edges[i].To()))
            mst.push_back(edges[i]);
    return mst;
}

int main() {
    ifstream cin("apm.in");
    ofstream cout("apm.out");
    int v, e;
    cin >> v >> e;
    vector<Edge> edges;
    for (; e > 0; --e) {
        int from, to, cost;
        cin >> from >> to >> cost;
        edges.push_back(Edge(--from, --to, cost));
    }
    vector<Edge> mst = Kruskal(v, edges);
    int totalCost = 0;
    for (int i = 0; i < int(mst.size()); ++i)
        totalCost += mst[i].Cost();
    cout << totalCost << "\n" << int(mst.size()) << "\n";
    for (int i = 0; i < int(mst.size()); ++i)
        cout << mst[i].From() + 1 << " " << mst[i].To() + 1 << "\n";
    cin.close();
    cout.close();
    return 0;
}