#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 <std::tuple<int, int>> muchii;

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
    for(int i = 0; i < N; i++)
        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(componente[x] != componente[y]) {
            //trebuie sa punem toate nodurile componentelor in aceeasi componenta
            for(int j = 0; j < N; j++) {
                if(componente[j] == comp) {
                    componente[j] = componente[x];
                }
            }
            //tinem minte muchia ca fiind pusa
            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';
}