#include <stdio.h>
#include <vector>

using namespace std;

struct edge
{
    int node,cost;
};

vector <edge> e[200001];

edge aux;
bool v[200001];
int h[200001],p[200001],c[200001],d[200001],sol[2][200000],a,b,n,m,q,r,s,nr;

void percolate(int x)
{
    while ((x>1)&&(c[x]<c[x/2]))
    {
        a=p[h[x]];p[h[x]]=p[h[x/2]];p[h[x/2]]=a;
        a=h[x];h[x]=h[x/2];h[x/2]=a;
        a=c[x];c[x]=c[x/2];c[x/2]=a;
        a=d[x];d[x]=d[x/2];d[x/2]=a;
        x/=2;
    }
}

void sift (int x)
{
    while (((2*x<=nr)&&(c[x]>c[2*x]))||((2*x<nr)&&(c[x]>c[2*x+1])))
    {
        if ((2*x<nr)&&(c[2*x+1]<c[2*x]))
        {
            a=p[h[x]];p[h[x]]=p[h[2*x+1]];p[h[2*x+1]]=a;
            a=h[x];h[x]=h[2*x+1];h[2*x+1]=a;
            a=c[x];c[x]=c[2*x+1];c[2*x+1]=a;
            a=d[x];d[x]=d[2*x+1];d[2*x+1]=a;
            x=2*x+1;
        }
        else
        {
            a=p[h[x]];p[h[x]]=p[h[2*x]];p[h[2*x]]=a;
            a=h[x];h[x]=h[2*x];h[2*x]=a;
            a=c[x];c[x]=c[2*x];c[2*x]=a;
            a=d[x];d[x]=d[2*x];d[2*x]=a;
            x*=2;
        }
    }
}

int main()
{
    int i,x,y,z;
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    scanf("%d%d",&n,&m);
    for (i=1;i<=m;++i)
    {
        scanf("%d%d%d",&x,&y,&z);
        aux.node=y;aux.cost=z;
        e[x].push_back(aux);
        aux.node=x;
        e[y].push_back(aux);
    }
    v[1]=1;r=e[1].size();p[1]=-1;
    for (i=0;i<r;++i)
    {
        ++nr;aux=e[1][i];
        c[nr]=aux.cost;
        h[nr]=aux.node;
        d[nr]=1;
        p[aux.node]=nr;
        percolate(nr);
    }
    for (q=1;q<n;++q)
    {
        b=h[1];
        r=e[b].size();
        s+=c[1];v[b]=1;
        sol[0][q]=d[1];
        sol[1][q]=b;
        for (i=0;i<r;++i)
            if (!v[e[b][i].node])
            {
                aux=e[b][i];
                if (!p[aux.node])
                {
                    ++nr;
                    p[aux.node]=nr;c[nr]=aux.cost;h[nr]=aux.node;d[nr]=b;
                    percolate(nr);
                }
                else
                {
                    if (c[p[aux.node]]>aux.cost)
                    {
                        c[p[aux.node]]=aux.cost;
                        d[p[aux.node]]=b;
                        percolate(p[aux.node]);
                    }
                }
            }
        h[p[b]]=h[nr];p[h[nr]]=p[b];c[p[b]]=c[nr];d[p[b]]=d[nr];--nr;
        sift(p[b]);
    }
    printf("%d\n%d\n",s,n-1);
    for (i=1;i<n;++i)
        printf("%d %d\n",sol[0][i],sol[1][i]);
    return 0;
}