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

using namespace std;

struct edge {
    int x, y;
    int cost;

    edge(int _x, int _y, int _cost): x(_x), y(_y), cost(_cost) {}
};

struct comp {
    bool operator() (const edge& lhs, const edge& rhs) const {
        return lhs.cost < rhs.cost;
    }
};

class disjoint_set {
private:
    vector<int> parent;
    vector<int> rank;

public:
    disjoint_set(int N) {
        rank.resize(N + 1, 0);
        parent.resize(N + 1);

        for (int i = 1; i <= N; ++i)
            parent[i] = i;
    }

    int find(int x) {
        if (x == parent[x])
            return x;

        return parent[x] = find(parent[x]);
    }

    void unite(int x, int y) {
        int px = find(x);
        int py = find(y);

        if (rank[px] < rank[py])
            parent[px] = py;
        else
            parent[py] = px;

        if (rank[px] == rank[py])
            ++rank[px];
    }
};

int mst(vector<edge>& edges, int N)
{
    disjoint_set ds(N);

    int total = 0;
    vector<edge> solution;
    vector<edge>::iterator it;
    for (it = edges.begin(); it != edges.end(); ++it) {
        int x = it->x;
        int y = it->y;
        int cst = it->cost;

        if (ds.find(x) != ds.find(y)) {
            total += cst;
            solution.push_back(*it);
            ds.unite(x, y);
        }
    }

    ofstream fout("apm.out");

    fout << total << "\n";
    fout << solution.size() << "\n";

    for (it = solution.begin(); it != solution.end(); ++it)
        fout << it->x << " " << it->y << "\n";
}

int main()
{
    ifstream fin("apm.in");

    int N, M;
    fin >> N >> M;

    vector<edge> edges;
    for (int i = 0; i < M; ++i) {
        int x, y, cst;
        fin >> x >> y >> cst;
        edges.push_back(edge(x, y, cst));
    }
    fin.close();

    sort(edges.begin(), edges.end(), comp());
    mst(edges, N);

    return 0;
}