#include <stdio.h>
#include <algorithm>
#include <bitset>

using namespace std;
FILE* f, * g;
int n, m, tata[200002], rang[200002], ss, arbore[400002][3], tot;
bitset <200002>fr;
typedef struct
{
    int n1, n2, c;
}pereche;
pereche v[400002];

bool cm(pereche p, pereche q)
{
    return (p.c < q.c);
}

void read()
{
    int i;
    fscanf(f, "%d %d", &n, &m);
    for (i = 1;i <= m;++i)
        fscanf(f, "%d %d %d", &v[i].n1, &v[i].n2, &v[i].c);
    sort(v + 1, v + m + 1, cm);
}

int multime(int nod)///determin multimea din care face parte nodul nod
{
    if (tata[nod] != nod)///nu am ajuns la radacina, adica tatal nodului nu coincide cu nodul
        tata[nod] = multime(tata[nod]);///modificam parintele nodului cu radacina arborelui din care face parte
    return tata[nod];
}

void change(int x, int y)
{
    x = multime(x);
    y = multime(y);
    /// if(x==y) return;
    if (rang[x] < rang[y])///unesc multimea cu rang mai mic de cea cu rang mai mare
        tata[x] = y;
    else
        tata[y] = x;
    if (rang[x] == rang[y])
        ++rang[x];
}


void solve()
{
    int i, x, y;
    for (i = 1;i <= n;++i)
        tata[i] = i, rang[i] = 0;///initial tatal fiecarui nod va fi el insusi si rangul fiecarui nod va fi 0
    int cost;
    for (i = 1;i <= m;++i)
    {
        x = v[i].n1;
        y = v[i].n2;
        cost = v[i].c;
        if (multime(x) != multime(y))///nu fac parte din aceiasi multime
        {
            change(x, y);
            ss += cost;
            ++tot;
            arbore[tot][1] = x;
            arbore[tot][2] = y;
        }
    }

}

void write()
{
    fprintf(g, "%d\n", ss);
    fprintf(g, "%d\n", tot);
    for (int i = 1;i <= tot;++i)
        fprintf(g, "%d %d\n", arbore[i][1], arbore[i][2]);
}

int main()
{
    int i, j, x, y;
    f = fopen("apm.in", "r");
    g = fopen("apm.out", "w");

    read();
    solve();
    write();

    fclose(f);
    fclose(g);
    return 0;
}