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

std::ifstream fin("apm.in");
std::ofstream fout("apm.out");

// void Initializare(int n, std::vector<int> &tata, std::vector<int> &h)
// {
//     for (int i = 1; i <= n; i++)
//     {
//         tata[i] = 0;
//         h[i] = 0;
//     }
// }

int Radacina(int i, std::vector<int> tata)
{
    while (tata[i] != 0)
        i = tata[i]; // caut radacina (strambosul) principala a nodului
    return i;
}

void Reuneste(int u, int v, std::vector<int> &tata, std::vector<int> &h)
{
    int ru, rv;
    ru = Radacina(u, tata);
    rv = Radacina(v, tata);
    if (h[ru] > h[rv]) // se unesc 2 subarbori prin 2 noduri, iar nodul cu inaltimea cea mai mare este declarat tata
        tata[rv] = ru;
    else
    {
        tata[ru] = rv;
        if (h[ru] == h[rv]) // in cazul in care cele doua noduri se afla la aceeasi inaltime, se alege tatal aleatoriu si se incrementeaza inaltimea
            h[rv]++;
    }
}

void addEdge(std::vector<std::vector<int>> &edgeList, int u, int v, int w)
{
    edgeList.push_back({w, u, v});
}

void Kruskall(std::vector<std::vector<int>> &edgeList, int n)
{
    std::sort(edgeList.begin(), edgeList.end()); // sortarea vectorului de muchii in functie de costuri

    std::vector<int> tata(n + 1, 0); // initializarea vectorului de tati
    std::vector<int> h(n + 1, 0);    // Iniitializarea vectorului de inaltime
    std::vector<std::vector<int>> muchii;

    int cost_total = 0;

    for (auto edge : edgeList)
    {
        int nod1 = edge[1];
        int nod2 = edge[2];
        int cost = edge[0];
        if (Radacina(nod1, tata) != Radacina(nod2, tata)) // Daca nu se poate forma un ciclu prin unirea celor doua muchii, le unim si adunam costul
        {
            Reuneste(nod1, nod2, tata, h);
            muchii.push_back({nod1, nod2});
            cost_total += cost;
        }
    }
    fout << "Costul minim: " << cost_total << '\n';
    fout << muchii.size() << '\n';
    for (auto muchie : muchii)
        fout << muchie[0] << " " << muchie[1] << '\n';
}

int main()
{
    int n, m;
    std::vector<std::vector<int>> edgeList;
    fin >> n >> m;
    for (int i = 0; i < m; i++)
    {
        int u, v, w;
        fin >> u >> v >> w;
        addEdge(edgeList, u, v, w);
    }
    Kruskall(edgeList, n);
    return 0;
}