#include<stdio.h>
#define Nmx 200001
#define INF 200000002

int n,m,U[Nmx],nr,nrr;

struct v
{
    int x,y;
}a[Nmx];
//heap
struct hp
{
    int x,y,c;
}Heap[Nmx];

//structura de nod
struct nod
{
    int inf;
    int cost;
    nod *urm;
};

nod *G[Nmx];


//inseram noduri in graf
void insert(int x,int y,int c)
{
    nod *aux;
    aux=new nod;
    aux->urm=G[x];
    aux->inf=y;
    aux->cost=c;
    G[x]=aux;
}

//functia de citire
void citire()
{
    int x,y,c;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i)
    {
        scanf("%d%d%d",&x,&y,&c);
        insert(x,y,c);
        insert(y,x,c);
    }
}

void intersch(hp &x,hp &y)
{
    hp aux;
    aux=x;
    x=y;
    y=aux;
}

//bagam un nod in heap
void push(int k)
{
    int t;
    while(k>1&&Heap[k/2].c>Heap[k].c)
    {
        intersch(Heap[k],Heap[k/2]);
        k=k/2;
    }
}
void scot(int k)
{
    while((k*2<=nr&&Heap[k*2].c<Heap[k].c)||
          (k*2+1<=nr&&Heap[k*2+1].c<Heap[k].c))
    {
        if(k*2+1<=nr)
         {
          if(Heap[k*2].c<Heap[k*2+1].c)
          {
            intersch(Heap[k],Heap[k*2]);
            k=k*2;
          }
        else{
            intersch(Heap[k],Heap[k*2+1]);
            k=k*2+1;
           }
         }
       else {
            intersch(Heap[k],Heap[k*2]);
            k=k*2;
        }
    }

}



void solve()
{
    U[1]=1;
    int sum=0;
    int Nrs=1;
    //bagam in heap muchiile incidente cu primul nod
    for(nod *p=G[1];p!=NULL;p=p->urm)
    {
        Heap[++nr].x=1;
        Heap[nr].y=p->inf;
        Heap[nr].c=p->cost;
        push(nr);
    }
    //finsih
    while(Nrs<n)
    {
        int ok=0;
        while(!ok)
        {
            int min,nf=0,nd=0;
            min=Heap[1].c;
            nf=Heap[1].x;
            nd=Heap[1].y;
            if(U[nd]==0&&U[nf]==1)
            {
                U[nd]=1;
                Heap[1]=Heap[nr--];
                scot(1);
                sum+=min;
                a[++nrr].x=nf;
                a[nrr].y=nd;
                for(nod *p=G[nd];p!=NULL;p=p->urm)
                {
                    if(U[p->inf]==0)
                    {
                        Heap[++nr].c=p->cost;
                        Heap[nr].x=nd;
                        Heap[nr].y=p->inf;
                        push(nr);
                    }
                }
                ok=1;
            }
            else { Heap[1]=Heap[nr--];
                  scot(1);
            }
        }

        Nrs++;
    }
    printf("%d\n%d\n",sum,n-1);
    for(int i=1;i<Nrs;i++)
        printf("%d %d\n",a[i].x,a[i].y);
}


//functia principala
int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    citire();
    solve();
    return 0;
}