#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;

struct muchie
{
    unsigned long int a; //Sursa
    unsigned long int b; //Destinatie
    int cost; //Cost
    bool apartine_apm; //Daca muchia apartine APM
};

unsigned long int n; //Nr. de varfuri
unsigned long int m; //Nr. de muchii
muchie muchii[400001]; //Muchiile
long long int cost_apm; //Costul arborelui
unsigned long int componente[200001]; //Componentele conexe

inline bool comparare_muchii(muchie a, muchie b)
{
    if (a.cost < b.cost)
        return true;
    else
        return false;
}
inline void citire()
{
    ifstream fin("apm.in");
    fin >> n >> m;
    for (unsigned long int i = 0; i < m; i++)
    {
        fin >> muchii[i].b >> muchii[i].a >> muchii[i].cost;
        muchii[i].apartine_apm = false;
    }
    fin.close();
}
inline void kruskal()
{
    cost_apm = 0;
    for (unsigned long int i = 1; i <= n; i++)
        componente[i] = i; //Fiecare nod e o componenta conexa
    sort(&muchii[0], &muchii[m], comparare_muchii); //Sortam muchiile dupa cost
    unsigned long int c_muchie = 0; //Contorul in vectorul de muchii
    unsigned long int muchii_adaugate = 0; //Nr. de muchii din APM
    unsigned long int c_modificata; //Valoarea componentei celui de-al doilea nod al muchiei
    while (muchii_adaugate < (n - 1))
    {
        //APM-ul are n-1 muchii
        if (componente[muchii[c_muchie].a] != componente[muchii[c_muchie].b])
        {
            //Daca muchia contine noduri din componente diferite, aceasta poate fi adaugata
            c_modificata = componente[muchii[c_muchie].b];
            for (unsigned long int i = 1; i <= n; i++)
                if (componente[i] == c_modificata)
                    componente[i] = componente[muchii[c_muchie].a]; //Toate elementele componentei b se adauga la a
            cost_apm = cost_apm + muchii[c_muchie].cost; //Modificam costul arborelui
            muchii[c_muchie].apartine_apm = true; //Muchia apartine APM
            muchii_adaugate++; //Incrementam numarul de muchii al APM
        }
        c_muchie++;
    }
}
inline void scriere()
{
    ofstream fout("apm.out");
    fout << cost_apm << "\n" << n-1 << "\n";
    for (unsigned long int i = 0; i < m; i++)
        if (muchii[i].apartine_apm == true)
            fout << muchii[i].a << " " << muchii[i].b << "\n";
    fout.close();
}
int main()
{
    citire();
    kruskal();
    scriere();
    return 0;
}