#include <cstdio>
#include <vector>
#include <algorithm>
#define DIM 400005
using namespace std;

int x[DIM], y[DIM], ind[DIM], n, m, gr[DIM], c[DIM];

struct ceva
{
    int i, j;
};

vector<ceva> Vans;

int comp(int i, int j)
{
    return c[i]<c[j];
}

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

int main()
{
    FILE *f = fopen("apm.in", "r");
    fscanf(f, "%d%d", &n, &m);
    for (int i = 1; i <= m; ++i)
        fscanf(f, "%d%d%d", &x[i], &y[i], &c[i]), ind[i] = i;
    fclose(f);

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

    sort(ind + 1, ind + m + 1, comp);

    int cost = 0; ceva cevaa;
    cevaa.i = 0;
    Vans.push_back(cevaa);
    for (int i = 1; i <= m; ++i)
    {
        if (grupa(x[ind[i]]) != grupa(y[ind[i]]))
        {
            gr[grupa(x[ind[i]])] = grupa(y[ind[i]]);
            cost += c[ind[i]];
            cevaa.i = x[ind[i]];
            cevaa.j = y[ind[i]];
            ++Vans[0].i;
            Vans.push_back(cevaa);
        }
    }

    f = fopen("apm.out", "w");
    fprintf(f, "%d\n%d\n", cost, Vans[0].i);

    for (int i = 1; i <= Vans[0].i; ++i)
        fprintf (f, "%d %d\n", Vans[i].i, Vans[i].j);

    return 0;
}