#include<cstdio>
#include<algorithm>

using namespace std;

const int nmax=200005;

struct muchie
{
    int x,y,c;
}edge[2*nmax],st[nmax];

int t[nmax],h[nmax];

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

inline int findset(int x)
{
    while(t[x]!=x)
        x=t[x];
    return x;
}

inline void unionset(int tx,int ty)
{
    if(h[tx]==h[ty])
    {
        h[tx]++;
        t[ty]=tx;
    }
    else if(h[tx]>h[ty])
        t[ty]=tx;
    else
        t[tx]=ty;
}


int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    int n,m,sum=0,i;
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;++i)
        scanf("%d%d%d",&edge[i].x,&edge[i].y,&edge[i].c);
    sort(edge+1,edge+m+1,cmp);
    for(i=1;i<=n;++i)
        t[i]=i,h[i]=1;
    int cnt,tx,ty;
    for(i=1,cnt=0;cnt<n-1;++i)
    {
        tx=findset(edge[i].x);
        ty=findset(edge[i].y);
        if(tx!=ty)
        {
            sum+=edge[i].c;
            unionset(tx,ty);
            st[++cnt]=edge[i];
        }
    }
    printf("%d\n",sum);
    printf("%d\n",n-1);
    for(i=1;i<=cnt;++i)
        printf("%d %d\n",st[i].x,st[i].y);
}