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

const int INF = 1e9;

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

Result
prim(int n, const auto &adj) {
    int total_weight = 0;
    vector<bool> visited(n + 1, false);
    vector<int> parents(n + 1, -1);
    vector<int> min_w(n + 1, INF);

    min_w[1] = 0;
    vector<pair<int, int>> mst_edges;

    for (int i = 1; i <= n; i++) {
        int u = -1;

        for (int j = 1; j <= n; j++) {
            if (!visited[j] && (u == -1 || min_w[j] < min_w[u]))
                u = j;
        }

        visited[u] = true;
        total_weight += min_w[u];
        if (parents[u] != -1)
            mst_edges.push_back({u, parents[u]});

        for (int j = 1; j <= n; j++) {
            if (!visited[j] && adj[u][j] < INF && adj[u][j] < min_w[j]) {
                min_w[j]  = adj[u][j];
                parents[j] = u;
            }
        }
    }

    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<int>> adj(n + 1, vector<int>(n + 1, INF));
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u][v] = adj[v][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;
}