#include <bits/stdc++.h>
#include <chrono>

using namespace std;

struct edge {
    int x, y;
    int w;
    bool operator<(const edge& other) const {
        return this->w < other.w;
    }
};

int V, E;

int findSetRoot(int *set, int nod)
{
    if (set[nod] == nod)
        return nod;
    return set[nod] = findSetRoot(set, set[nod]);
}

int main(int argc, char** argv)
{
    if (argc < 3)
        exit(EXIT_FAILURE);
    ifstream in(argv[1]);
    ofstream out(argv[2]);
    in >> V >> E;
    int cost_curent = 0;
    int nr_muchii_max = V-1;
    vector<edge> muchii(E);
    vector<edge> mst;
    mst.reserve(E);
    int *set = new int[V + 1];
    auto start = chrono::high_resolution_clock::now();
    for (auto& elem : muchii)
        in >> elem.x >> elem.y >> elem.w;
    ranges::sort(muchii, [](const edge& a, const edge& b) -> bool {
        return a < b;
    });
    for (int i = 1; i <= V; ++i) {
        set[i] = i;
    }
    for (auto &elem: muchii) {
        auto root_x = findSetRoot(set, elem.x);
        auto root_y = findSetRoot(set, elem.y);
        if (root_x != root_y)
        {
            cost_curent += elem.w;
            mst.push_back(elem);
            set[root_y] = root_x;
        }
    }
    auto custom_sort = [](const edge& u, const edge& w) {
        if(u.x == w.x)
            return u.y < w.y;
        return u.x < w.x;
    };
    sort(mst.begin(), mst.end(), custom_sort);
    out << cost_curent << '\n' << V-1 << '\n';
    for (auto &elem: mst)
        out << elem.x << ' ' << elem.y << '\n';
    auto end = chrono::high_resolution_clock::now();
    auto duration = chrono::duration_cast<chrono::milliseconds>(end-start);
    cout << duration.count() << "ms" << endl;
}