#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

int main() {
    std::ifstream input("apm.in");
    std::ofstream output("apm.out");

    int n, m;
    input >> n >> m;
    std::vector<std::vector<std::pair<int, int>>> graph(n + 1);

    while (m--) {
        int x, y, c;
        input >> x >> y >> c;
        graph[x].emplace_back(y, c);
        graph[y].emplace_back(x, c);
    }

    std::vector<bool> in_apm(n + 1, false);

    auto cmp = [](const std::pair<int, int> &lhs, const std::pair<int, int> &rhs) {
        return lhs.second > rhs.second;
    };

    std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, decltype(cmp)> queue(cmp);
    std::vector<int> dist(n + 1, INT32_MAX);
    std::vector<int> root(n + 1, 0);
    dist[1] = 0;
    queue.emplace(1, 0);

    while (!queue.empty()) {
        auto top = queue.top();
        queue.pop();
        if (in_apm[top.first]) continue;

        in_apm[top.first] = true;

        for (const auto &x: graph[top.first]) {
            if (!in_apm[x.first]) {
                int candidate = x.second;
                if (candidate < dist[x.first]) {
                    dist[x.first] = candidate;
                    root[x.first] = top.first;
                    queue.emplace(x.first, candidate);
                }
            }
        }
    }
    int sum = 0;
    for (int i = 1; i <= n; ++i) sum += dist[i];
    output << sum << '\n' << n - 1 << '\n';

    for (int i = 2; i <= n; ++i) output << i << " " << root[i] << '\n';

    return 0;
}