#include <bits/stdc++.h>

struct Edge {
    int from, to, cost;
};

int rad(std::vector<int>& P, int x) {
    int y = x;
    while (x != P[x]) {
        x = P[x];
    }
    while (P[y] != x) {
        int aux = P[y];
        P[y] = x;
        y = aux;
    }
    return x;
}

int main() {
    assert(freopen("apm.in", "r", stdin));
    int V, E;
    assert(scanf("%d %d ", &V, &E) == 2);
    std::vector<Edge> Graph(E);
    int x, y, w;
    for (int i = 0; i < E; ++i) {
        assert(scanf("%d %d %d ", &x, &y, &w) == 3);
        Graph[i] = Edge {--x, --y, w};
    }
    fclose(stdin);
    std::sort(Graph.begin(), Graph.end(), [] (Edge& a, Edge& b) {return a.cost < b.cost;});

//    for (auto& e : Graph) {
//        std::cout << e.from << ' ' << e.to << ' ' << e.cost << '\n';
//    }

    std::vector<int> P(V);
    for (int i = 0; i < V; i++) P[i] = i;

    std::vector<int> res(V - 1);
    int sum = 0, k = 0;

    for (int i = 0; i < E && k < V - 1; i++) {
        int x = rad(P, Graph[i].from);
        int y = rad(P, Graph[i].to);
        if (x == y) continue;
        P[x] = y;
        sum += Graph[i].cost;
        res[k++] = i;
    }

    assert(freopen("apm.out", "w", stdout));
    printf("%d\n%d\n", sum, res.size());
    for (size_t i = 0; i < res.size(); ++i) {
        printf("%d %d\n", Graph[res[i]].from + 1, Graph[res[i]].to + 1);
    }
    fclose(stdout);

    return 0;
}