#include <fstream>
#include <vector>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");

void minimum_spanning_tree(int n, const vector<vector<pair<int, int>>>& adj) {
    vector<bool> in_mst(n + 1, false);
    vector<int> min_edge(n + 1, 1e9);
    vector<int> parent(n + 1, -1);
    min_edge[1] = 0;

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

        in_mst[u] = true;

        for (const auto& [v, weight] : adj[u]) {
            if (!in_mst[v] && weight < min_edge[v]) {
                min_edge[v] = weight;
                parent[v] = u;
            }
        }
    }

    int total_cost = 0;
    for (int i = 2; i <= n; ++i) {
        total_cost += min_edge[i];
    }

    fout << total_cost << '\n' << n - 1 << '\n';
    for (int i = 2; i <= n; ++i) {
        fout << parent[i] << ' ' << i << '\n';
    }
}

int main() {
    int n, m;
    fin >> n >> m;
    vector<vector<pair<int, int>>> adj(n + 1);

    for (int i = 0; i < m; ++i) {
        int u, v, weight;
        fin >> u >> v >> weight;
        adj[u].emplace_back(v, weight);
        adj[v].emplace_back(u, weight);
    }

    minimum_spanning_tree(n, adj);
    return 0;
}