#include <fstream>
#include <iostream>

#define Nmax 200001
#define Mmax 400002

using namespace std;

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

int n, m, tata[Nmax], x, y, c, fx, fy, sum, i, M;

struct mu {int cost, x, y;} Muchie[Mmax];
struct {int x, y;} A[Nmax];

void qsort (int left, int right)
{
    int i, j, x;
    mu aux;
    i = left;
    j = right;

    x = Muchie[(left + right) / 2].cost;
    do
    {
        while (Muchie[i].cost < x)
            i ++;
        while (x < Muchie[j].cost)
            j --;

        if (i <= j)
        {
            aux = Muchie[i];
            Muchie[i++] = Muchie[j];
            Muchie[j--] = aux;
        }
    } while (i <= j);

    if (left < j)
        qsort(left, j);
    if (i < right)
        qsort(i, right);
}

int f (int x)
{
    if (tata[x] == x)
        return x;
    return tata[x] = f(tata[x]);
}

int main()
{
    fin >> n >> m;
    for (i = 1; i <= m; i ++)
    {
        fin >> Muchie[i].x >> Muchie[i].y >> Muchie[i].cost;
    }
    qsort(1, m);

    for (i = 1; i <= n; i ++)
        tata[i] = i;

    for (i = 1; i <= m; i ++)
    {
        x = Muchie[i].x;
        y = Muchie[i].y;

        fx = f (x);
        fy = f (y);

        if (fx != fy)
        {
            A[++M].y = x;
            A[M].x = y;
            if (fx > fy)
                tata[fx] = fy;
            else
                tata[fy] = fx;

            sum += Muchie[i].cost;
        }
    }

    fout << sum << '\n' << M << '\n';
    for (i = 1; i <= M; i ++)
    {
        fout << A[i].x << " " << A[i].y << '\n';
    }

    fin.close();
    fout.close();
    return 0;
}