#include<cstdio>
#include<algorithm>

using namespace std;
int t[200005],h[200005];
struct citit
{
    int x,y,c;
};
citit v[400005];
citit sol[400005];
int findmd(int x)
{
    while(x!=t[x])
        x=t[x];
    return x;
}
bool cmp(citit a,citit b)
{
    return a.c<b.c;
}
bool unionset(int x,int y){
    int tx,ty;
    tx=findmd(x);
    ty=findmd(y);
    if(tx==ty)
        return 0;
    if(h[tx]==h[ty])
    {
        h[tx]++;
        t[ty]=tx;
    }
    else
        if(h[tx]<h[ty])
            t[tx]=ty;
        else
            t[ty]=tx;
        return 1;
}
int main(){
    int n ,m,k,i,cost,x,y;
    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].x,&v[i].y,&v[i].c);
    }
    sort(v+1,v+m+1,cmp);
    for(i=1;i<=n;i++)
    {
        t[i]=i;
        h[i]=1;
    }
    k=0;
    cost =0;
    for(i=1;i<=m&&k<n-1;i++)
    {
        x=v[i].x;
        y=v[i].y;
        if(unionset(x,y))
        {
            cost+=v[i].c;
            sol[++k] = v[i];
        }
    }
    printf("%d\n%d\n",cost,k);
    for(i=1;i<=k;i++)
        printf("%d %d\n",sol[i].x,sol[i].y);
    return 0;
}