///Pentru citire, afisare
#include <cstdio>

///Pentru sort
#include <algorithm>

using namespace std;

FILE *f, *g;

///Muchii
struct muchia
{
    int st, dr;
    int c;
};

muchia v[400001];

///Componenta conexa
int comp[200001];

///Arborele partial de cost minim
int rez;

int muchie[400001];
int muchii;

int n, m;

///Citirea datelor
void readFile()
{
    f = fopen("apm.in", "r");

    fscanf(f, "%d%d", &n, &m);

    int i;
    for(i = 1; i <= m; i ++)
        fscanf(f, "%d%d%d", &v[i].st, &v[i].dr, &v[i].c);

    fclose(f);
}

///Returneaza componenta conexa lui i in O(log*N);
int compConexa(int i)
{
    if(comp[i] == i)
        return i;

    comp[i] = compConexa(comp[i]);

    return comp[i];
}

///Unifica componentele conexe a si b
int reuniune(int a, int b)
{
    comp[compConexa(a)] = compConexa(b);
}

///Obtine arborele partial de cost minim
void getArb()
{
    int i;

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

    int c1, c2;

    for(i = 1; i <= m; i ++)
    {
        ///c1, c2: Componentele conexe ale extremitatilor
        c1 = compConexa(v[i].st);
        c2 = compConexa(v[i].dr);

        ///Daca acestea sunt diferite (nu creeaza ciclu)
        if(c1 != c2)
        {
            ///Aduna costul
            rez += v[i].c;

            ///Unifica componentele conexe
            reuniune(c1, c2);

            ///Adauga muchia la rezultat
            muchie[++ muchii] = i;
        }
    }
}

///Compara costul
bool cmp(muchia a, muchia b)
{
    return (a.c < b.c);
}

void solve()
{
    ///radixSort nu merge pe negative
    sort(v + 1, v + m + 1, cmp);

    getArb();
}

void printFile()
{
    g = fopen("apm.out", "w");

    fprintf(g, "%d\n%d\n", rez, muchii);

    int i;
    int poz;
    for(i = 1; i <= muchii; i ++)
    {
        poz = muchie[i];

        fprintf(g, "%d %d\n", v[poz].st, v[poz].dr);
    }

    fclose(g);
}

int main()
{
    readFile();

    solve();

    printFile();

    return 0;
}