#include <bits/stdc++.h>
#define NMAX 200009

typedef std::tuple<int, int> edge;
#define get_cost(t) std::get<0>(t)
#define get_neighbour(t) std::get<1>(t)

class Task {
 public:
    void solve() {
        read_input();
        get_result();
        print_output();
    }

    int n, m, cost_apm, root;
    std::vector<int> d, p;
    std::vector<edge> G[NMAX];
    std::vector<edge> apm;
    std::priority_queue<edge, std::vector<edge>, std::greater<edge>> pq;
    std::bitset<NMAX> used;

    void read_input() {
        std::cin >> n >> m;

        for (int i = 1, x, y, c; i <= m; ++i) {
            std::cin >> x >> y >> c;
            G[x].push_back(edge(c, y));
            G[y].push_back(edge(c, x));
        }
        cost_apm = 0;
    }

    void get_result() {
        p = std::vector<int>(n + 1, 0);
        d = std::vector<int>(n + 1, INT_MAX);

        root = 1;
        d[root] = 0;
        p[root] = 0;
        pq.push(edge(d[root], root));

        for (int i = 1; i <= n; ++i) {
            std::tuple<int, int> e;
            int node;
            do {
            e = pq.top();
            pq.pop();

            node = get_neighbour(e);
            } while (used[node]);

            cost_apm += d[node];
            used[node] = 1;

            for (auto it = G[node].begin(); it != G[node].end(); ++it) {
                int neighbour = get_neighbour(*it), cost = get_cost(*it);

                if (!used[neighbour] && cost < d[neighbour]) {
                    d[neighbour] = cost;
                    p[neighbour] = node;
                    pq.push(edge(d[neighbour], neighbour));
                }
            }
        }
    }

    void print_output() {
        std::cout << cost_apm << "\n";
        std::cout << n - 1 << "\n";
        for (int i = 1; i <= n; ++i) {
            if (i != root) {
                std::cout << i << " " << p[i] << "\n";
            }
        }
    }
};

int main() {
    auto cin_buff = std::cin.rdbuf();
    auto cout_buff = std::cout.rdbuf();

    std::ifstream fin("apm.in");
    std::cin.rdbuf(fin.rdbuf());

    std::ofstream fout("apm.out");
    std::cout.rdbuf(fout.rdbuf());

    Task *task = new Task();
    task->solve();
    delete task;

    std::cin.rdbuf(cin_buff);
    std::cout.rdbuf(cout_buff);
    return 0;
}