#include <bits/stdc++.h>

using namespace std;

struct Edge {
    int x, y, c;
};

bool cmp(Edge a, Edge b) {
    return a.c < b.c;
}

pair<int, vector<pair<int, int>>> Prim(int n, int m, vector<Edge>& edges) {
    vector<vector<pair<int, int>>> adj(n + 1);
    for (const auto& edge : edges) {
        adj[edge.x].emplace_back(edge.y, edge.c);
        adj[edge.y].emplace_back(edge.x, edge.c);
    }

    vector<int> d(n + 1, INT_MAX);
    vector<int> parent(n + 1, -1);
    vector<bool> inHeap(n + 1, true);

    auto cmp = [&](pair<int, int> a, pair<int, int> b) { return a.second > b.second; };
    priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> pq(cmp);

    d[1] = 0;
    pq.emplace(1, d[1]);

    while (!pq.empty()) {
        auto [node, cost] = pq.top();
        pq.pop();
        inHeap[node] = false;

        for (auto &[neighbor, weight] : adj[node]) {
            if (inHeap[neighbor] && weight < d[neighbor]) {
                d[neighbor] = weight;
                parent[neighbor] = node;
                pq.emplace(neighbor, d[neighbor]);
            }
        }
    }

    vector<pair<int, int>> mst_edges;
    int total_cost = 0;
    for (int i = 2; i <= n; i++) {
        mst_edges.emplace_back(i, parent[i]);
        total_cost += d[i];
    }

    return {total_cost, mst_edges};
}


int main() {
    ifstream f("apm.in");
    ofstream g("apm.out");
    int n, m;
    f >> n >> m;
    vector<Edge> edges(m);
    for (int i = 0; i < m; i++) {
        f >> edges[i].x >> edges[i].y >> edges[i].c;
    }
    auto [apm, mst_edges] = Prim(n, m, edges);
    g << apm << '\n';
    g << mst_edges.size() << '\n';
    for (const auto &edge : mst_edges) {
        g << edge.first << ' ' << edge.second << '\n';
    }
    return 0;
}