#include <fstream>
#include <vector>
#include <tuple>
#include <algorithm>

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

std::vector <std::tuple<int, int, int>> lista_muchii;
std::vector <int> componente;
std::vector <int> ct_componente;
std::vector <std::tuple<int, int>> muchii;

int Find(int nod)
{
    if(componente[nod] == nod)
        return nod;
    //PATH COMPRESSION
    return componente[nod] = Find(componente[nod]);
}

void Union(int x, int y)
{
    x = Find(x);
    y = Find(y);
    //optimizare pt a avea un arbore cat mai echilibrat
    if(ct_componente[x] > ct_componente[y])
        componente[y] = x;
    else componente[x] = y;
}


int main()
{
    int N, M;
    int x, y, c, s = 0;
    fin >> N >> M;
    //memoram intr un vector tupluri de forma nod x -> nod y si costul muchiei dintre acestia
    for(int i = 0; i < M; i++)
    {
        fin >> x >> y >> c;
        std::tuple <int, int, int> t = {x - 1, y - 1, c};
        lista_muchii.push_back(t);
    }
    //sortam muchiile dupa costul lor in ordine crecatoare
    std::sort(lista_muchii.begin(), lista_muchii.end(), [](const std::tuple<int, int, int> &a, const std::tuple<int, int, int> &b){
        return std::get<2>(a) < std::get<2>(b);
    });

    //trebuie sa initializam fiecare nod ca fiind intr-o componenta conexa diferita
    //si sa memoram faptul ca au doar un nod in acea componenta
    for(int i = 0; i < N; i++)
    {
        //comp dif
        componente.push_back(i);
        //1 nod
        ct_componente.push_back(i);
    }
    //acum fiecare nod reprezinta o componenta conexa diferita si trebuie sa le unim prin muchii
    int nr_muchii = 0, size = lista_muchii.size();
    //cand nr_muchii ajunge la N - 1 inseamnca ca am legat nodurile si avem apcm - ul
    for(int i = 0; i < size && nr_muchii != N - 1; i++)
    {
        x = std::get<0>(lista_muchii[i]);
        y = std::get<1>(lista_muchii[i]);
        int comp = componente[y];
        if(Find(x) != Find(y)) {
            //trebuie sa punem toate nodurile componentelor in aceeasi componenta
            //tinem minte muchia ca fiind pusa
            Union(x, y);
            muchii.push_back(std::make_tuple(x, y));
            nr_muchii ++;
            //adunam la suma apcm - ului
            s += std::get<2>(lista_muchii[i]);
            }

        }
    fout << s << '\n';
    fout << nr_muchii << '\n';
    size = muchii.size();
    for(int i = 0; i < size; i++)
        fout << std::get<0>(muchii[i]) + 1 << " " << std::get<1>(muchii[i]) + 1 << '\n';
}