#include <iostream>
#include <fstream>

#include <vector>
#include <queue>
#include <unordered_set>

#define NMAX 200000


void find_mst(std::vector<std::pair<int, int>> adj[], int &min_sum, std::vector<std::pair<int, int>> &mst)
{
    int initial_node = 0;
    std::unordered_set<int> used;
    std::priority_queue<std::tuple<int, int, int>,
                        std::vector<std::tuple<int, int, int>>,
                        std::greater<std::tuple<int, int, int>>> pq;

    min_sum = 0;

    used.insert(initial_node);

    for (auto [neigh, cost] : adj[initial_node])
        pq.push({cost, initial_node, neigh});

    while (!pq.empty()) {
        auto [cost, parent, node] = pq.top();
        pq.pop();

        if (used.find(node) != used.end())
            continue;

        min_sum += cost;
        mst.push_back({parent, node});
        used.insert(node);
        parent = node;

        for (auto [neigh, cost] : adj[node])
            pq.push({cost, parent, neigh});
    }
}

int main()
{
    std::ifstream fin("apm.in");
    std::ofstream fout("apm.out");

    int n, m;
    std::vector<std::pair<int, int>> adj[NMAX];
    int msts;
    std::vector<std::pair<int, int>> mst;


    fin >> n >> m;

    for (int v, w, c, i = 0; i < m; ++i) {
        fin >> v >> w >> c;

        adj[v - 1].push_back({w - 1, c});
        adj[w - 1].push_back({v - 1, c});
    }


    find_mst(adj, msts, mst);


    fout << msts << '\n' << mst.size() << '\n';

    for (auto &edge : mst)
        fout << edge.first + 1 << ' ' << edge.second + 1 << '\n';

    fin.close();
    fout.close();

    return 0;
}