#include <cstdio>

FILE* in=fopen("meta.in","r");
FILE* out=fopen("meta.out","w");

const int Q=10006,W=300005,INF=2000000000;

int v[Q][Q];

int n,m;

int tata[Q],cost[Q];
bool term[Q];

void verifarb()
{
    int rez=0;

    for(int i=2; i<=n; i++)
    {
        rez+=v[i][tata[i]];
    }

    fprintf(out,"%d\n%d\n",rez,n-1);

    for(int i=2; i<=n; i++)
        fprintf(out,"%d %d\n",i,tata[i]);
}


int h[Q],nh;
int where[Q];

void swap(int p1, int p2)
{
    int aux;
    aux=where[h[p1]];
    where[h[p1]]=where[h[p2]];
    where[h[p2]]=aux;

    aux=h[p1];
    h[p1]=h[p2];
    h[p2]=aux;
}

void coboara(int p)
{
    int p0=p;

    if(2*p<=nh && cost[h[p0]]>cost[h[2*p]])
        p0=2*p;
    if( (2*p+1)<=nh && cost[h[p0]]>cost[h[2*p+1]])
        p0=2*p+1;

    if(p!=p0)
    {
        swap(p,p0);
        coboara(p0);
    }
}

void urca(int p)
{
    if(p!=1 && cost[h[p/2]]>cost[h[p]])
    {
        swap(p/2,p);
        urca(p/2);
    }
}

void push(int x)
{
    nh++;
    h[nh]=x;
    where[x]=nh;
    urca(nh);
}

void eject(int p)
{
    if(p==nh)
    {
        nh--;
    }
    else
    {
        swap(nh,p);
        nh--;
        coboara(p);
        urca(p);
    }
}

int main()
{
    fscanf(in,"%d%d",&n,&m);

    for(int i=1; i<=n; i++)
        cost[i]=INF;

    int a,b,c;

    for(int i=1; i<=m; i++)
    {
        fscanf(in,"%d%d%d",&a,&b,&c);
        v[a][b]=c;
        v[b][a]=c;
    }

    push(1);

    cost[1]=0;

    int act;

    for(int k=1; k<=n; k++)
    {
        act=h[1];
        eject(1);
        term[act]=1;

        for(int i=1; i<=n; i++)
        {
            if(term[i]!=1 && v[i][act]!=0)
            {
                if(v[act][i]<cost[i])
                {
                    cost[i]=v[act][i];
                    tata[i]=act;

                    if(where[i]!=0)
                        eject(where[i]);

                    push(i);
                }
            }
        }
    }

    verifarb();

    return 0;
}