#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 parent;
    std::unordered_set<int> used;
    std::priority_queue<std::pair<int, int>,
                        std::vector<std::pair<int, int>>,
                        std::greater<std::pair<int, int>>> pq;

    min_sum = 0;

    parent = 0;

    used.insert(parent);

    for (auto edge : adj[parent])
        pq.push({edge.second, edge.first});

    while (!pq.empty()) {
        auto [cost, 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 edge : adj[parent])
            pq.push({edge.second, edge.first});
    }
}

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;
}