#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, vector<int>& sets) {
    if (sets[nod] == nod) {
        return nod;
    }
    sets[nod] = get_set(sets[nod], sets);
    return sets[nod];
}

void make_union(int n1, int n2, vector<int>& sets) {
    sets[get_set(n1, sets)] = get_set(n2, sets);
}

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);
    int min_cost = 0;

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

    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);
            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;
}