#include <cstdio>
#include <vector>
#include <algorithm>
#include <ctime>

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;
    scanf("%d%d", &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) {
        scanf ("%d%d%d", &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;
            }
        }
    }

    printf("%d\n%lu\n", min_cost, ama.size());
    for (const Edge& edge : ama) {
        printf("%d %d\n", edge.n1, edge.n2);
    }
    return 0;
}