#include <fstream>
#include <algorithm>

using namespace std;

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

int x[400005], y[400005], cost[400005], indice[400005], gr[200005], sol[400005];
int n, m;

int grupa (int x)
{
    if (gr[x] == x)
        return x;

    gr[x] = grupa(gr[x]);
        return gr[x];
}

void uneste (int x, int y)
{
    gr[grupa(x)] = grupa(y);
}

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

    for (int i = 1; i <= m; i ++)
    {
        f >> x[i] >> y[i] >> cost[i];
        indice[i] = i;
    }

    for (int i = 1; i <= n; i ++)
        gr[i] = i;
}

bool cmp (int a, int b)
{
    return (cost[a] < cost[b]);
}

int main()
{
    int cost_min = 0, nr_muchii = 0;

    citire ();

    sort (indice + 1, indice + m + 1, cmp);

    for (int i = 1; i <= m; i ++)
        if (grupa(x[indice[i]]) != grupa(y[indice[i]]))
        {
            sol [++ nr_muchii] = indice[i];
            cost_min += cost[indice[i]];

            uneste (x[indice[i]], y[indice[i]]);
        }

    g << cost_min << '\n' << nr_muchii << '\n';

    for (int i = 1; i <= nr_muchii; i ++)
        g << y[sol[i]] << " " << x[sol[i]] << '\n';

    f.close ();
    g.close ();
    return 0;
}