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

using namespace std;

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

unsigned int n, m;

vector <unsigned int> T, Rang;
vector <pair <unsigned int, unsigned int> > sol;

int APM;

struct muchie
{
    unsigned int x, y;
    int cost;
};

vector <muchie> muchii;

bool compara(muchie a, muchie b)
{
    return a.cost < b.cost;
}

unsigned int radacina(unsigned int x)
{
    unsigned int R, y;

    for (R = x; T[R] != R; R = T[R]);

    while (T[x] != x)
    {
        y = T[x];
        T[x] = R;
        x = y;
    }

    return R;
}

void unire(unsigned int x, unsigned int y)
{
        if (Rang[x] > Rang[y])
            T[y] = x;
        else
            T[x] = y;

        if (Rang[x] == Rang[y])
            Rang[y]++;
}

void setup()
{
    f >> n >> m;

    T = Rang = vector <unsigned int> (n + 1, 0);

    for (unsigned int i = 1; i <= m; i++)
    {
        unsigned int x, y;
        int cost;

        f >> x >> y >> cost;

        muchii.push_back({x, y, cost});
    }

    for (unsigned int i = 1; i <= n; i++)
        T[i] = i;

    sort(muchii.begin(), muchii.end(), compara);
}

void kruskal()
{
    for (unsigned int i = 0; i < muchii.size(); i++)
    {
        unsigned int rx = radacina(muchii[i].x), ry = radacina(muchii[i].y);

        if (rx != ry)
        {
            unire(rx, ry);
            APM += muchii[i].cost;
            sol.push_back(make_pair(muchii[i].x, muchii[i].y));
        }
    }
}

void show()
{
    g << APM << '\n' << n - 1 << '\n';

    for (unsigned int i = 0; i < sol.size(); i++)
    {
        g << sol[i].first << ' ' << sol[i].second << '\n';
    }
}

int main()
{
    setup();
    kruskal();
    show();

    return 0;
}