#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9;

struct Result {
    int total_weight;
    vector<pair<int, int>> edges;
};

using Edge = pair<int, int>;

Result
prim(int n, const auto &adj) {
    int total_weight = 0;
    vector<Edge> mst_edges;
    vector<int> parent(n + 1, -1);
    vector<int> min_dist(n + 1, INF);
    vector<int> visited(n + 1, false);

    priority_queue<Edge,  vector<Edge>, greater<Edge>> pq;

    min_dist[1] = 0;
    pq.push({0, 1});

    while (!pq.empty()) {
        int cost = pq.top().first;
        int u = pq.top().second;
        pq.pop();

        if (visited[u]) continue;

        visited[u] = true;
        total_weight += cost;

        if (parent[u] != -1)
            mst_edges.push_back({u, parent[u]});

        for (auto &e : adj[u]) {
            int v = e.first;
            int w = e.second;

            if (!visited[v] && w < min_dist[v]) {
                min_dist[v] = w;
                parent[v] = u;
                pq.push({w, v});
            }
        }
    }

    return {total_weight, mst_edges};
}

int main(int argc, char const *argv[])
{
    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);

    int n, m;
    cin >> n >> m;

    vector<vector<Edge>> adj(n + 1, vector<Edge>());
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }

    auto res = prim(n, adj);
    cout << res.total_weight << "\n";
    cout << n - 1 << "\n";
    for (auto ed : res.edges)
        cout << ed.first << " " << ed.second << "\n";
    return 0;
}