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

using namespace std;

struct Edge {
    int n1, n2, cost;

    Edge() {}
    Edge(int n1, int n2, int cost) : n1(n1), n2(n2), cost(cost) {}
};

bool compare_edges(const Edge& e1, const Edge& e2) {
    return e1.cost < e2.cost;
}

int get_set(int nod, const vector<int>& sets) {
    while (sets[nod] != nod) {
        nod = sets[nod];
    }
    return nod;
}

void make_union(int n1, int n2, vector<int>& sets, vector<int>& heights) {
    int root1 = get_set(n1, sets);
    int root2 = get_set(n2, sets);
    if (heights[root1] < heights[root2]) {
        sets[root1] = root2;
    } else {
        sets[root2] = root1;
        if (heights[root2] == heights[root1]) {
            heights[root1]++;
        }
    }
}

int main() {
    freopen ("apm.in", "r", stdin);
    freopen ("apm.out", "w", stdout);
    int N, M;
    cin >> N >> M;
    vector<Edge> edges(M);
    vector<Edge> ama;
    vector<int> sets(N + 1);
    vector<int> heights(N + 1);
    int min_cost = 0;

    for (int i = 1; i <= N; i++) {
        sets[i] = i;
        heights[i] = 1;
    }

    for (int i = 0; i < M; ++i) {
        cin >> edges[i].n1 >> edges[i].n2 >> edges[i].cost;
    }

    sort(edges.begin(), edges.end(), compare_edges);
    N--;
    for (int i = 0; i < M; i++) {
        if (get_set(edges[i].n1, sets) != get_set(edges[i].n2, sets)) {
            make_union(edges[i].n1, edges[i].n2, sets, heights);
            min_cost += edges[i].cost;
            ama.push_back(edges[i]);
            if (ama.size() == N) {
                break;
            }
        }
    }
    cout << min_cost << "\n";
    cout << ama.size() << "\n";
    for (const Edge& edge : ama) {
        cout << edge.n1 << " " << edge.n2 << "\n";
    }

    return 0;
}