#include <stdio.h>
#include <string.h>
#define maxn 200010
const int inf=1000000;
struct lista
{
    int nod,cost;
    lista *next;
};
lista *g[maxn],*p;
int h[maxn],d[maxn],poz[maxn],t[maxn],sol[maxn],n,m,j,lg,i,c,min,cost;
void push(int i,int j,int c)
{
    lista *p=new lista;
    p->nod=j;
    p->cost=c;
    p->next=g[i];
    g[i]=p;
}
void swap(int i,int j)
{
    int t=h[i]; h[i]=h[j]; h[j]=t;
}
void upheap(int x)
{
    while(x/2 && d[h[x]]<d[h[x/2]])
    {
        swap(x,x/2);
        poz[h[x]]=x;
        poz[h[x/2]]=x/2;
        x/=2;
    }
}
void downheap(int x)
{
    int y=0;
    while(x!=y)
    {
        y=x;
        if(y*2<=lg && d[h[x]]>d[h[2*y]]) x=y*2;
        if(y*2+1<=lg && d[h[x]]>d[h[2*y+1]]) x=y*2+1;
        swap(x,y);
        poz[h[x]]=x;
        poz[h[y]]=y;
    }
}
void remove()
{
    swap(1,lg);
    poz[h[1]]=1;
    lg--;
    downheap(1);
}
void insert(int x)
{
    h[++lg]=x;
    poz[h[lg]]=lg;
    upheap(lg);
}
int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(; m--; )
    {
        scanf("%d%d%d",&i,&j,&c);
        push(i,j,c); push(j,i,c);
    }
    memset(d,inf,sizeof(d));
    memset(t,1,sizeof(t));
    d[1]=0;
    insert(1);

    while(lg)
    {
        min=h[1];
        remove();
        cost+=d[min];
        sol[min]=t[min];
        for(p=g[min]; p!=NULL; p=p->next)
         if(d[p->nod]>p->cost)
         {
             d[p->nod]=p->cost;
             t[p->nod]=min;
             if(poz[p->nod]) upheap(poz[p->nod]);
             else insert(p->nod);
         }
    }
    printf("%d\n%d\n",cost,n-1);
    for(i=2; i<=n; i++)
     printf("%d %d\n",sol[i],i);
    return 0;
}