#include <stdio.h>
#define max 200010
#define inf 10000
struct lista
{
    int nod,cost;
    lista *next;
};
lista *g[max],*p;
int n,m,i,j,min,pmin,k,e,t[max],d[max],sol[max],nr,cost;
char u[max];
void push(int i,int j,int cost)
{
    lista *p=new lista;
    p->cost=cost;
    p->nod=j;
    p->next=g[i];
    g[i]=p;
}
int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(i=1; i<=n; i++) t[i]=1,d[i]=inf; d[1]=0;
    for(k=1; k<=m; k++)
    {
        scanf("%d%d%d",&i,&j,&e);
        push(i,j,e);
        push(j,i,e);
        if(i==1) d[j]=e;
        if(j==1) d[i]=e;
    }
    u[1]=1;
    while(1)
    {
        min=inf; pmin=-1;
        for(i=1; i<=n; i++)
         if(!u[i] && min>d[i])
          min=d[i],pmin=i;
        if(min==inf) break;
        u[pmin]=1; cost+=d[pmin];
        sol[pmin]=t[pmin]; ++nr;
        p=g[pmin];
        while(p)
        {
            if(d[p->nod]>p->cost)
            {
                d[p->nod]=p->cost;
                t[p->nod]=pmin;
            }
            p=p->next;
        }
    }
    printf("%d\n%d\n",cost,nr);
    for(i=1; i<=n; i++)
     if(sol[i]!=0) printf("%d %d\n",sol[i],i);
    return 0;
}