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

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

struct v
{
    int x,y;
}a[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 solve()
{
    U[1]=1;
    int sum=0;
    int Nrs=1;
    while(Nrs<n)
    {
        int min=INF,pzmin=0,nd=0;
        for(int i=1;i<=n;++i)
         if(!U[i])
         {
            for(nod *p=G[i];p!=NULL;p=p->urm)
              if(U[p->inf]==1&&p->cost<min)
               {
                    min=p->cost;
                    pzmin=i;
                    nd=p->inf;
               }
         }
        sum=sum+min;
        U[pzmin]=1;
        a[++nr].x=pzmin;
        a[nr].y=nd;
        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;
}