#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

//std::ifstream fin("C:\\Users\\DellMX\\CLionProjects\\AF_Lab2\\apm.in");
//std::ofstream fout("C:\\Users\\DellMX\\CLionProjects\\AF_Lab2\\apm.out");
std::ifstream fin("apm.in");
std::ofstream fout("apm.out");

int n, m;
std::vector<std::pair<int, std::pair<int, int>>> perechi;
std::vector<int> tata, h;
std::vector<std::pair<int, int>> solutie;

void initializare(int u) {
    h[u] = 0;
    tata[u] = u;
}

int reprezentant(int u) {
    while (tata[u]) {
        u = tata[u];
    }
    return u;
}

void reuneste(int u, int v) {
    int ru, rv;
    ru = reprezentant(u);
    rv = reprezentant(v);
    if (h[ru] > h[rv]) {
        tata[rv]= ru;
    }
    else {
        tata[ru] = rv;
        if (h[ru] == h[rv]) {
            h[rv] = h[rv] + 1;
        }
    }
}

int main() {
    fin >> n >> m;
    tata.resize(n + 1);
    h.resize(n + 1);
    int x, y, cost, suma = 0, m_nou;
    for (int i = 0; i < m; i++) {
        fin >> x >> y >> cost;
        perechi.push_back({cost, {x, y}});
    }

    std::sort(perechi.begin(), perechi.end());

    for (auto &pereche : perechi) {
        int u = pereche.second.first;
        int v = pereche.second.second;

        int tata_u = reprezentant(u);
        int tata_v = reprezentant(v);

        if (tata_u != tata_v) {
            solutie.push_back({u, v});

            suma += pereche.first;
            m_nou++;

            reuneste(tata_u, tata_v);
        }
    }

    fout << suma << " " << m_nou << "\n";
    for (int i = 0; i < m_nou; i++) {
        fout << solutie[i].second << " " << solutie[i].first << "\n";
    }

    return 0;
}