#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 main(int argc, char** argv)
{
    ifstream in("apm.in");
    ofstream out("apm.out");
    in >> V >> E;
    int cost_curent = 0;
    vector<edge> muchii(E);
    vector<edge> mst;
    mst.reserve(E);
    short *set = new short[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) {
        if(set[elem.x] != set[elem.y]) {
            cost_curent += elem.w;
            mst.push_back(elem);
            int set_y = set[elem.y];
            for (int j = 1; j <= V; j++)
                if(set[j] == set_y)
                    set[j] = set[elem.x];
        }
    }
    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;
}