#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);
    }

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
    vector<bool> in_mst(n + 1, false);
    vector<pair<int, int>> mst_edges;
    int total_cost = 0;

    pq.emplace(0, 1);  // Începem de la nodul 1

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

        if (in_mst[node]) continue;
        in_mst[node] = true;
        total_cost += cost;

        for (auto &[neighbor, weight] : adj[node]) {
            if (!in_mst[neighbor]) {
                pq.emplace(weight, neighbor);
                mst_edges.emplace_back(node, neighbor);
            }
        }
    }

    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;
}