//graf neorientat, arbore partial de cost minim, PRIM
#include <iostream>
#include <fstream>
#define NMAX 200000
#define MMAX 400000
using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");

int n; //numar noduri
int m; //numar muchii
int S; //suma muchiilor din arborele partial de cost minim

struct lista{ //structura listelor de adiacenta
//informatie utila
    int vecin;
    int cost;
//informatie de legatura
    struct lista *urm;
}*L[NMAX+2],*p;

int nrh;
struct coadaAsteptare{
    int nod;
    int tata;
}heap[NMAX+2]; //heap cu noduri adiacente arborelui
    int d[NMAX+2]; //d[i] - distanta minima de la nodul i din heap la un vecin al sau
    int poz[NMAX+2]; //poz[i] - pozitia nodului i in heap (0, daca nu exista)
int mch[2*NMAX+2],nrm; //vector muchii folosite in arborele partial de cost minim

void citeste()
{
    int x,y,c;
    in>>n>>m;
    for(int i=1;i<=m;++i)
    {
        in>>x>>y>>c;
        //adauga y la lista x
        p=new lista;
        p->vecin=y;
        p->cost=c;
        p->urm=L[x];
        L[x]=p;
        //adauga x la lista y
        p=new lista;
        p->vecin=x;
        p->cost=c;
        p->urm=L[y];
        L[y]=p;
    }
}
int tata(int x){
    return x/2;
}
int fiu_st(int x){
    return 2*x;
}
int fiu_dr(int x){
    return 2*x+1;
}
void interschimba(int &a,int &b){
    int aux=a;
    a=b, b=aux;
}
void interschimba(coadaAsteptare &a,coadaAsteptare &b){
    coadaAsteptare aux=a;
    a=b, b=aux;
}

void infiltreaza(int x)
{//urca nodul de pe pozitia x la locul lui in heap
    int pz=x;
    while(pz>1) //cat timp exista tata
    {
        if(d[pz]<d[tata(pz)]) //daca merita interschimbarea
        {
            interschimba(heap[pz],heap[tata(pz)]); //interschimba nodurile in heap,
            interschimba(poz[heap[pz].nod],poz[heap[tata(pz)].nod]); //pozitiile lor in heapd
            interschimba(d[pz],d[tata(pz)]); //si distantele acestora
            pz = tata(pz);
        }
        else //termina structura
            pz = 1;
    }
}

void cerne(int x)
{//coboara nodul de pe pozitia x la locul lui in heap
    int pz=x;
    while(pz<=nrh/2) //cat timp exista fii
    {
        int fiu = fiu_st(pz);
        if(fiu+1<=nrh) //daca exista si fiu dreapta
            if(d[fiu+1]<d[fiu]) //si daca fiul dreapta se afla la distanta mai mica
                fiu = fiu_dr(pz);

        if(d[pz]>d[fiu]) //daca merita interschimbarea
        {
            interschimba(heap[pz],heap[fiu]); //interschimba nodurile in heap,
            interschimba(poz[heap[pz].nod],poz[heap[fiu].nod]); //pozitiile lor in heap
            interschimba(d[pz],d[fiu]); //si distantele acestora
            pz = fiu;
        }
        else //altfel opreste structura
            pz = n;
    }
}

void actualizeazaHeap()
{
    //muta ultimul nod pe prima pozitie
    heap[1]=heap[nrh];
    poz[heap[1].nod]=1;
    d[1]=d[nrh];
    nrh--;

    //coboara nodul 1 la locul lui in heap
    cerne(1);
}

void prim(int st)
{
    int ant,nod;

    ant=st;
    poz[st]=-1;
    //adauga vecinii nodului de start in heap
    p=L[st];
    while(p!=NULL)
    {
        heap[++nrh].nod=p->vecin; //adauga nodul la sfarsitul heapului
        heap[nrh].tata=ant;
            poz[heap[nrh].nod]=nrh;
            d[nrh]=p->cost;
        infiltreaza(nrh); //urca nodul in pozitia corespunzatoare
        p=p->urm;
    }
    //construieste arborele partial de cost minim, golind heapul
    while(nrh>0) //cat timp exista noduri in heap
    {
        nod=heap[1].nod; //extrage primul nod din heap (si adauga-l in arbore)
            S=S+d[1];
            poz[heap[1].nod]=-1;
            d[1]=0;
        mch[++nrm]=heap[1].tata, mch[++nrm]=heap[1].nod; //retine muchia adaugata in arbore
        actualizeazaHeap(); //actualizeaza heap

        //adauga in heap toti vecinii nodului extras
        p=L[nod];
        while(p!=NULL)
        {
            if(poz[p->vecin]!=-1) //daca vecinul nu se afla in arbore (nu a fost deja vizitat) SI
            {
                if(poz[p->vecin]==0) //daca vecinul nu se afla in heap
                {
                    heap[++nrh].nod=p->vecin; //adauga vecinul la sfarsitul heapului
                    heap[nrh].tata=nod;
                        poz[heap[nrh].nod]=nrh;
                        d[nrh]=p->cost;
                    infiltreaza(nrh); //urca vecinul in pozitia corespunzatoare
                }
                else //altfel (daca vecinul se afla deja in heap)
                {
                    if(d[poz[p->vecin]] > p->cost)
                    {
                        d[poz[p->vecin]] = p->cost; //actualizeaza distanta
                        heap[poz[p->vecin]].tata = nod; //SI tatal nodului
                    }
                    infiltreaza(poz[p->vecin]); //urca vecinul in pozitia corespunzatoare
                }
            }
            p=p->urm;
        }

        ant=nod;
    }
}

int main()
{
    citeste();
/*
    for(int i=1;i<=n;++i)
    {
        p=L[i]; out<<i<<": ";
        while(p!=NULL)
        {
            out<<p->vecin<<" ";
            p=p->urm;
        }
        out<<"\n";
    }
*/
//determina arborele partial de cost minim
    prim(1);
//afiseaza muchiile ce constituie arborele partial de cost minim si suma acestora
    out<<S<<"\n"<<n-1<<"\n";
    for(int i=1;i<=2*(n-1);i+=2)
        out<<mch[i]<<" "<<mch[i+1]<<"\n";

    return 0;
}