#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 union find 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 dupa regula de ponderare)
*/
//r[i] retine adancimea arborelui
//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 incepand de la x
    //din acel arbore, nodurile situate sub x nu vor fi compresate!
    int rad=x;
    while(t[rad]!=0)
        rad=t[rad];
    //compresia caii
    int tmp;
    while(t[x]!=0)
    {
        tmp=t[x];
        t[x]=rad;
        x=tmp;
    }
    return rad;
}

void uniune(int rad1,int rad2)
{
    /*aplica uniunea a doi arbori, dupa rang, arborele cu rang mai mic se uneste la arborele cu rang mai mare
    radacina arborelui mai mic va avea ascendent radacina arborelui mai mare
    evident randul arborelui mai mare nu creste prin uniune
    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;
    else
        if(r[rad1]<r[rad2])
            t[rad1]=rad2;
        else
        {
            t[rad2]=rad1;
            r[rad1]++;
        }
}

//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
    fout<<cApm<<"\n"<<n-1<<"\n";
    for(i=0;i<apm.size();i++)
        fout<<apm[i].x<<" "<<apm[i].y<<"\n";
    fin.close();
    fout.close();
    return 0;
}