#include <bits/stdc++.h>

using namespace std;

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

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

    vector<int> d(n + 1, INT_MAX), p(n + 1, -1);
    vector<bool> vis(n + 1, false);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
    d[1] = 0;
    pq.push({0, 1});

    while (!pq.empty()) {
        int node = pq.top().second;
        pq.pop();

        if (vis[node]) continue;
        vis[node] = true;

        for (auto &[neighbor, cost] : G[node]) {
            if (!vis[neighbor] && d[neighbor] > cost) {
                d[neighbor] = cost;
                p[neighbor] = node;
                pq.push({d[neighbor], neighbor});
            }
        }
    }

    vector<pair<int, int>> mst_edges;
    for (int i = 2; i <= n; i++) {
        if (p[i] != -1) {
            mst_edges.push_back({p[i], i});
        }
    }
    return 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;
    }
    vector<pair<int, int>> mst_edges = Prim(n, m, edges);
    int apm = 0;
    for (const auto &edge : mst_edges) {
        for (const auto &e : edges) {
            if ((e.x == edge.first && e.y == edge.second) || (e.x == edge.second && e.y == edge.first)) {
                apm += e.c;
                break;
            }
        }
    }
    g << apm << '\n';
    g << mst_edges.size() << '\n';
    for (const auto &edge : mst_edges) {
        g << edge.first << ' ' << edge.second << '\n';
    }
    return 0;
}