#include <fstream>
#include <iostream>

#define LIM_M 401
#define LIM_N 200001

using namespace std;

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

struct muchie
{
    int inc;
    int sf;
    int cost;
};

muchie sm[LIM_M], arbore[LIM_M];
int n, m, nms, csfm, comp[LIM_N], j, ca;

void citire()
{
    int i;

    fin >> n >> m;
    for (i = 1; i <= m; i++)
        fin >> sm[i].inc >> sm[i].sf >> sm[i].cost;
}

void initcomp()
{
    int i;

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

void sortm()
{
    int i;
    bool AmSchimbat;
    muchie aux;

    do
    {
        AmSchimbat = false;
        for (i = 1; i <= m - 1; i++)
            if (sm[i].cost > sm[i + 1].cost) // Nu sunt in ordinea corecta
            { 
                aux = sm[i];
                sm[i] = sm[i + 1];
                sm[i + 1] = aux;
                AmSchimbat = true;
            }
    } while (AmSchimbat);
}

void rezultat()
{
    fout << ca << '\n' << n - 1 << '\n';
    for (int i = 1; i <= nms; i++) // pentru toate muchiile selectate
        fout << arbore[i].inc << ' ' << arbore[i].sf << '\n';

}

void arata_comp() {
    for (int j = 1; j <= n; j++) {
        cout << comp[j] << ' ';
    }
    cout << endl;
}

int main()
{
    int i;

    citire();
    initcomp();
    //arata_comp();
    sortm();
    for (i = 1; nms <= n - 2; i++) // Se vor selecta n - 1 muchii.
        if (comp[sm[i].inc] != comp[sm[i].sf]) // Extremitatile muchiei curente sunt in componente conexe diferite.
        {
            nms++; // Selectam inca o muchie.
            arbore[nms] = sm[i]; // Retinem muchia in arbore.
            ca += sm[i].cost; // Actualizam costul arborelui.
            csfm = comp[sm[i].sf]; // Retinem numarul de componenta al sfarsitului muchiei.
            for (j = 1; j <= n; j++) // Actualizam numerele de componenta conexa.
                if (comp[j] == csfm) 
                    comp[j] = comp[sm[i].inc]; // Modificam numarul de componenta conexa.
            //arata_comp();
        }
    rezultat();
}

/*
4 8 1 +
1 2 2 +
4 7 2 +
7 8 2
1 4 3 +
3 6 3 +
2 5 4 +
6 8 4 +
3 5 5
1 7 6
5 6 7
6 7 8
1 3 92
*/

/*
  A B C D E F G H - in prezentare
        j
  1 2 3 4 5 6 7 8
  1 1 3 4 5 6 4 4 - comp
  1 1 3 1 5 6 1 1
        *     * *


  1 2 3 4 5 6 7 8 - in fisierul de date  
  1 2 3 4 5 6 7 8 - in comp
  1 2 3 4 5 6 7 4
*/