#include <stdio.h>
#include <algorithm>

using namespace std;

struct edge
{
    int n1,n2,c;
};

inline bool cmp(edge a,edge b)
{
    return a.c<b.c;
}

edge v[400001];
int n,m,r[200001],s,sol[2][200001],i,j;

int update(int x,int y)
{
    if (r[r[x]]!=r[x])
        r[x]=update(r[x],y);
    else if (y) r[x]=y;
    return r[x];
}

int main()
{
    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",&v[i].n1,&v[i].n2,&v[i].c);
    sort(v+1,v+m+1,cmp);
    for (i=1;i<=n;++i)
        r[i]=i;
    for (i=1;i<=m;++i)
    {
        if (r[r[v[i].n1]]!=r[v[i].n1])
            r[v[i].n1]=update(v[i].n1,0);
        if (r[r[v[i].n2]]!=r[v[i].n2])
            r[v[i].n2]=update(v[i].n2,0);
        if (r[v[i].n1]!=r[v[i].n2])
        {
            r[v[i].n2]=update(r[v[i].n2],r[v[i].n1]);
            s+=v[i].c;++j;
            sol[0][j]=v[i].n1;
            sol[1][j]=v[i].n2;
        }
    }
    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;
}