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

using namespace std;

struct Muchie {
    int start, dest, cost;

    bool operator<(const Muchie& rhs) const {
        return cost > rhs.cost;
    }
};

int main()
{
    ifstream in("apm.in");

    int n;
    in >> n;

    vector<vector<pair<int, int>>> vecini(n);

    int m;
    in >> m;

    for (int i = 0; i < m; ++i) {
        int start, dest, cost;
        in >> start >> dest >> cost;

        --start;
        --dest;

        vecini[start].emplace_back(dest, cost);
        vecini[dest].emplace_back(start, cost);
    }

    vector<Muchie> apm;
    priority_queue<Muchie> muchii;

    int initial = 0;
    for (auto vecin : vecini[initial]) {
        int dest = vecin.first;
        int cost = vecin.second;
        muchii.push(Muchie { initial, dest, cost });
    }

    vector<bool> viz(n);
    viz[initial] = true;

    int costTotal = 0;

    while (!muchii.empty()) {
        auto m = muchii.top();
        muchii.pop();

        if (viz[m.dest]) {
            continue;
        }

        apm.emplace_back(m);
        costTotal += m.cost;

        int initial = m.dest;
        viz[initial] = true;
        for (auto vecin : vecini[initial]) {
            int dest = vecin.first;
            int cost = vecin.second;
            muchii.push(Muchie { initial, dest, cost});
        }
    }

    ofstream out("apm.out");
    out << costTotal << '\n';
    out << apm.size() << '\n';
    for (auto m : apm) {
        out << (m.start + 1) << ' ' << (m.dest + 1) << '\n';
    }
}