#include <cstdio>
#include <algorithm>

using namespace std;

struct muchie
{
    int x,y,c;
};

int indice[500001], sol[500001], m, n, nr, costm;
muchie v[400001];

bool cmp(muchie a, muchie b)
{
    return a.c < b.c;
}

int det(int x)
{
    int copie, i, y;
    copie = x;
    while(indice[copie] != copie)
        copie = indice[copie];
    while(x != indice[x])
    {
        y = indice[x];
        indice[x] = copie;
        x = y;
    }
    return copie;
}

void calculeaza()
{
    int i, nod1, nod2;
    for(i = 1; i <= m && nr < n - 1;i++)
    {
        nod1 = det(v[i].x);
        nod2 = det(v[i].y);
        if(nod1 != nod2)
        {
            costm += v[i].c;
            sol[++nr] = i;
            indice[nod1] = nod2;
        }
    }
}

int main()
{
    FILE *in, *out;
    in = fopen("apm.in", "r");
    out = fopen("apm.out", "w");
    int i, j;
    fscanf(in, "%d", &n);
    fscanf(in, "%d", &m);
    for(i = 1; i <= m; i++)
    {
        fscanf(in, "%d%d%d", &v[i].x, &v[i].y, &v[i].c);
    }
    sort(v+1, v+m+1, cmp);
    for(i = 1 ; i <= n ; i++)
        indice[i] = i ;
    calculeaza();
    fprintf(out, "%d\n%d\n", costm, nr);
    for(i = 1; i <= nr; i++)
        fprintf(out, "%d %d\n", v[sol[i]].y, v[sol[i]].x);
    return 0;
}