#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() {
    std::ifstream f("apm.in");
    int V, E;
    f >> V >> E;
    std::vector<Edge> Graph(E);
    for (int i = 0; i < E; ++i) {
        int x, y, c;
        f >> x >> y >> c;
        Graph[i] = Edge {--x, --y, c};
    }
    f.close();
    std::sort(Graph.begin(), Graph.end(), [] (Edge& a, Edge& b) {return a.cost < b.cost;});
    std::vector<int> P(V);
    for (size_t i = 0; i < P.size(); i++) P[i] = i;
    std::vector<std::pair<int, int>> res(V - 1);
    int k = 0;
    int cost = 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;
        res[k++] = {Graph[i].from, Graph[i].to};
        cost += Graph[i].cost;
    }
    std::ofstream g("apm.out");
    g << cost << '\n' << res.size() << '\n';
    for (size_t i = 0; i < res.size(); ++i) {
        g << res[i].first + 1 << ' ' << res[i].second + 1 << '\n';
    }
    g.close();
    return 0;
}