#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
#include <queue>
#include <climits>

std::ifstream fin("apm.in");
std::ofstream fout("apm.out");

struct Vecin {
    int v, cost;
};

void prim(int n, const std::vector<std::vector<Vecin>>& adj) {

    std::vector<int> d(n + 1, INT_MAX);
    std::vector<int> tata(n + 1, 0);
    std::vector<bool> vizitat(n + 1, false);

    using PII = std::pair<int, int>;
    std::priority_queue<PII, std::vector<PII>, std::greater<PII>> Q_heap;

    int start_node = 1;
    d[start_node] = 0;
    Q_heap.push({0, start_node});

    long long costTotal = 0;
    std::vector<std::pair<int, int>> apcm_edges;

    while (!Q_heap.empty()) {

        int u = Q_heap.top().second;
        int u_cost = Q_heap.top().first;
        Q_heap.pop();

        if (vizitat[u]) {
            continue;
        }

        vizitat[u] = true;
        costTotal += u_cost;

        if (tata[u] != 0) {
            apcm_edges.push_back({tata[u], u});
        }

        for (const auto& muchie : adj[u]) {
            int v = muchie.v;
            int cost_uv = muchie.cost;

            if (!vizitat[v] && cost_uv < d[v]) {
                d[v] = cost_uv;
                tata[v] = u;
                Q_heap.push({d[v], v});
            }
        }
    }

    fout << costTotal << "\n";
    fout << apcm_edges.size() << "\n";
    for (const auto& edge : apcm_edges) {
        fout << edge.first << " " << edge.second << "\n";
    }
}

int main() {
    int n, m;
    fin >> n >> m;

    std::vector<std::vector<Vecin>> adj(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v, cost;
        fin >> u >> v >> cost;
        adj[u].push_back({v, cost});
        adj[v].push_back({u, cost});
    }

    prim(n, adj);

    fin.close();
    fout.close();

    return 0;
}