#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

// Structura pentru muchie
struct Muchie
{
    int x, y, cost;
};

// Disjoint Set Union (Union-Find) pentru Kruskal
vector<int> parinte, rang;

int find(int x)
{
    if (parinte[x] != x)
        parinte[x] = find(parinte[x]); // path compression
    return parinte[x];
}

bool unite(int x, int y)
{
    int px = find(x);
    int py = find(y);

    if (px == py)
        return false; // deja in aceeasi componenta

    // union by rank
    if (rang[px] < rang[py])
        swap(px, py);
    parinte[py] = px;
    if (rang[px] == rang[py])
        rang[px]++;

    return true;
}

int main()
{
    int n, m;
    f >> n >> m;

    vector<Muchie> muchii(m);
    for (int i = 0; i < m; i++)
    {
        f >> muchii[i].x >> muchii[i].y >> muchii[i].cost;
    }

    // Initializare DSU
    parinte.resize(n + 1);
    rang.resize(n + 1, 0);
    for (int i = 1; i <= n; i++)
    {
        parinte[i] = i;
    }

    // Sortare muchii dupa cost
    sort(muchii.begin(), muchii.end(), [](const Muchie &a, const Muchie &b)
         { return a.cost < b.cost; });

    // Kruskal: selectam muchii in ordine crescatoare a costului
    long long costTotal = 0;
    vector<pair<int, int>> muchiiAPM;

    for (const Muchie &m : muchii)
    {
        if (unite(m.x, m.y))
        {
            costTotal += m.cost;
            muchiiAPM.push_back({m.x, m.y});

            // Arborele are exact N-1 muchii
            if ((int)muchiiAPM.size() == n - 1)
                break;
        }
    }

    // Afisare rezultat
    g << costTotal << "\n";
    g << muchiiAPM.size() << "\n";
    for (auto &muchie : muchiiAPM)
    {
        g << muchie.first << " " << muchie.second << "\n";
    }

    return 0;
}