#include<stdio.h>
#include<algorithm>
#define Nmax 200002
using namespace std;
int n,m,nh,s;
int list[Nmax];
int viz[Nmax];

struct graf
{
    int v,c;
    graf *adr;
};
graf *g[Nmax];

struct heap
{
    int v1,v2,c;
};
heap h[2*Nmax];

void graf_add(int v1,int v2,int c)
{
    graf *p;
    p=new graf;
    p->v=v2;
    p->c=c;
    p->adr=g[v1];
    g[v1]=p;
}

void heap_down(int x)
{
    int fs,fd,k;
    do
    {
        fs=x<<1;
        fd=fs+1;
        k=0;
        if(fs<=nh)
        {
            k=fs;
            if(fd<=nh && h[fd].c < h[fs].c)
                k=fd;
            if(h[k].c >= h[x].c)
                k=0;
        }
        if(k)
        {
            swap(h[x],h[k]);
            x=k;
        }
    }while(k);
}

void heap_up(int x)
{
    int t;
    t=x>>1;
    while(t>=1 && h[x].c < h[t].c)
    {
        swap(h[x],h[t]);
        x=t;
        t=x>>1;
    }
}

void heap_add(int v1,int v2,int c)
{
    ++nh;
    h[nh].v1=v1;
    h[nh].v2=v2;
    h[nh].c=c;
    heap_up(nh);
}

void heap_delete()
{
    h[1]=h[nh];
    --nh;
    heap_down(1);
}

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

void rezolv()
{
    int k,v1,v2,c;
    graf *p;
    nh=0;
    for(p=g[1];p;p=p->adr)
    {
        heap_add(1,p->v,p->c);
        list[p->v]=1;
    }
    viz[1]=1;
    s=0;
    k=1;
    while(k<=n)
    {
        v1=h[1].v1;
        v2=h[1].v2;
        c=h[1].c;
        heap_delete();
        if(viz[v2]==0)
        {
            ++k;
            s+=c;
            viz[v2]=1;
            list[v2]=v1;
            for(p=g[v2];p;p=p->adr)
                if(viz[p->v]==0)
                    heap_add(v2,p->v,p->c);
        }
    }
}

void scrie()
{
    int i;
    printf("%d\n%d\n",s,n-1);
    for(i=1;i<=n;++i)
        if(list[i])
            printf("%d %d\n",i,list[i]);
}

int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    citire();
    rezolv();
    scrie();
    fclose(stdin);
    fclose(stdout);
    return 0;
}