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

#define dim 200020
using namespace std;

//muchiile vor fi memorate cu o structura (x,y) muchia, c-costul
//se cere apm
//folosim Kruskal
//retin muchiile in vectorul de tip muchie m, le sortez crescator dupa cost
//aleg muchiile in ordine si daca nu se formeaza un ciclu, muchia face parte din apm si o retin in vectorul apm
//pentru a verifica daca nu se formeaza cicluri folosesc algoritmul de la paduri disjuncte si anume
//la inceput toate nodurile formeaza o multime(un arbore), iau o muchie si daca extremitatile fac parte din aceeasi arbore,
//se formeaza un ciclu, sar peste, altfel adaug la apm si maresc costul. Folosesc find pentru a cauta radacina arborelui si
//union pentru a uni subarborii (folosesc comprimarea caii si uniunea pe rang)

//r[i] retine 0 daca i nu este radacina si adancimea arborelui daca e
//padurile vor fi memorate cu vectorul de referinte ascendente, t[radacina]=0

int t[dim],r[dim];
int n,m1;//nr de noduri si nr de muchii

struct muchie
{
    int x,y,c;
};
vector<muchie>m,apm;

int find(int x)
{
    //caut radacina subarborelui in care se gaseste x si aplic compresia caii pentru toate nodurile din acel arbore
    int rad=x;
    while(t[rad]!=0)
        rad=t[rad];
    //compresia caii
    int y;
    while(t[x]!=0)
    {
        y=t[x];
        t[x]=rad;
        x=y;
    }
    return rad;
}

void uniune(int rad1,int rad2)
{
    //aplica uniunea a doi arbori, dupa rang, adica arborele cu rang mai mic se uneste la arborele cu rang mai mare,
    //adica radacina arborelui mai mic va avea ascendent radacina arborelui mai mare
    //evident randul arborelui mai mare nu creste prin uniune, iar rangul radacinii arborelui mai mic va fi 0, fiind alipit
    //daca rangul este egal inseamna ca rangul noului arbore va fi cu 1 mai mult
    //vom uni practic subarborii care au radacina rad1, respectiv rad2
    if(r[rad1]>r[rad2])
    {
        t[rad2]=rad1;
        r[rad2]=0;

    }
    else
        if(r[rad1]<r[rad2])
        {
            t[rad1]=rad2;
            r[rad1]=0;
        }
        else
        {
            t[rad2]=rad1;
            r[rad1]++;
            r[rad2]=0;
        }
}

//sortarea se face dupa cost si atunci ne trebuie o functie care sa spuna lui sort cum se face sortarea
bool compare(muchie a, muchie b)
{
    return a.c<=b.c;
}

int main()
{
    ifstream fin("apm.in");
    ofstream fout("apm.out");
    fin>>n>>m1;
    long long cApm=0;//aici voi memora costul apm
    int i,rad1,rad2;//i pentru a cicla de m ori, ext1 retine extremitatea1 resp extremitatea2 cand fac uniune
    muchie h;//retin muchia citita si apoi o copii in vectorul m
    for(i=0;i<m1;i++)
    {
        fin>>h.x>>h.y>>h.c;
        m.push_back(h);
    }
    //sortez crescator vectorul de muchii cu ajutorul fct compare
    sort(m.begin(),m.end(),compare);
    //apm va avea n-1 muchii, le iau in calcul pe toate din m pana cand am ales n-1 muchii
    int nr=1,j=0;
    while(nr<n && j<m1)
    {
        //aplica find pentru extremitatile muchiei si daca nu intoarce aceeasi valoare, adaug in apm si unesc subarborii
        rad1=find(m[j].x);
        rad2=find(m[j].y);
        if(rad1!=rad2)
        {
            cApm+=m[j].c;
            apm.push_back(m[j]);
            uniune(rad1,rad2);
            nr++;
        }
        j++;
    }
    //afisez costul total si muchiile din apm(puteam si din arborele creat)
    fout<<cApm<<"\n"<<n-1<<"\n";
    for(i=0;i<n-1;i++)
        fout<<apm[i].x<<" "<<apm[i].y<<"\n";
    fin.close();
    fout.close();
    return 0;
}