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

struct Nod
{
    int x,y,c;
};

bool cmp(Nod a,Nod b)
{
    return a.c<b.c;
}

Nod sol[400005];
int s;

Nod a[400005];
int n,m;
int c[200005];
void Citire()
{
    ifstream fin("apm.in");
    fin>>n>>m;
    for(int i=0;i<m;i++)
        fin>>a[i].x>>a[i].y>>a[i].c;
    fin.close();
    sort(a,a+m,cmp);

}

int Get(int x)
{
    if(x==c[x]) return x;
    c[x]=Get(c[x]);
    return c[x];
}

void Unify(int x,int y)
{
    //seful fostului sef al componentei lui y este
    //seful lui x
    c[Get(y)]=Get(x);
}


void Adauga(int i)
{
    s++;
    sol[s].x=a[i].x;
    sol[s].y=a[i].y;
    sol[s].c=sol[s-1].c+a[i].c;
}

void Rez()
{
    //nr = nr de componente conxe
    int nr=n;
    int i=0;
    //luam fiecare muchie in parte pentru a
    while(nr>1 && i<m)
    {
        int x=Get(a[i].x);
        int y=Get(a[i].y);
        //vedem sefii componentelor celor doua noduri ale
        //muchiei

        //daca sunt aceeasi inseamna ca nu e necesar sa
        //adaugam muchia la subgraful cu cost minim


        //altfel unificam cele doua componente
        //si adaugam muchia la subgraful de cost minim
        //si scade nr de componente
        if(x!=y)
        {
            Unify(a[i].x,a[i].y);
            Adauga(i);
            nr--;
        }
        i++;
    }
}

int main()
{
    Citire();
    //in citire sortam muchiile in functie de cost

    //c[i] = 'seful' componentei conexe in care se afla i
    for(int i=1;i<=n;i++)
        c[i]=i;
    //initializam fiecare nod fiind seful componentei conexe
    //a celei in care se afla (fiind singurul membru)


    Rez();

    ofstream fout("apm.out");
    fout<<sol[s].c<<"\n"<<s<<"\n";
    for(int i=1;i<=s;i++)
        fout<<sol[i].x<<" "<<sol[i].y<<"\n";

    return 0;
}