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

using namespace std;

struct Edge {
    int u, v, cost;

    Edge(int x, int y, int c) : u(x), v(y), cost(c) {}

    bool operator<(const Edge& other) const {
        return cost < other.cost;
    }
};

int find(int x, vector<int>& parent) {
    if (parent[x] != x)
        parent[x] = find(parent[x], parent);
    return parent[x];
}

void unite(int x, int y, vector<int>& parent, vector<int>& rank) {
    int rootX = find(x, parent);
    int rootY = find(y, parent);

    if (rootX != rootY) {
        if (rank[rootX] < rank[rootY])
            swap(rootX, rootY);
        else if (rank[rootX] == rank[rootY])
            rank[rootX]++;

        parent[rootY] = rootX;
    }
}

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

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

    vector<Edge> edges;
    for (int i = 0; i < M; ++i) {
        int x, y, c;
        fin >> x >> y >> c;
        edges.emplace_back(x, y, c);
    }

    // Sortăm muchiile în ordine crescătoare a costurilor
    sort(edges.begin(), edges.end());

    vector<int> parent(N + 1), rank(N + 1, 0);
    for (int i = 0; i <= N; ++i)
        parent[i] = i;

    int totalCost = 0;
    vector<Edge> minSpanningTree;

    for (const Edge& edge : edges) {
        if (find(edge.u, parent) != find(edge.v, parent)) {
            unite(edge.u, edge.v, parent, rank);
            totalCost += edge.cost;
            minSpanningTree.push_back(edge);
        }
    }

    fout << totalCost << endl;
    fout << minSpanningTree.size() << endl;

    for (const Edge& edge : minSpanningTree) {
        fout << edge.v << ' ' << edge.u << endl;
    }

    fin.close();
    fout.close();

    return 0;
}