#include <cstdio>
#include <algorithm>
using namespace std;
int t[200005],h[200005];
struct MUCHIE
{
    int u,v,c;
};
MUCHIE v[400005];
int Findset(int x)
{
    while (x!=t[x])
        x=t[x];
    return x;
}
bool unionset(int x,int y)
{
    int tx,ty;
    tx=Findset(x);
    ty=Findset(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;
}
bool cmp(MUCHIE a,MUCHIE b)
{
    return a.c<=b.c;
}
int sol[200005];
int main()
{
    freopen ("apm.in","r",stdin);
    freopen ("apm.out","w",stdout);
    int n,m,x,y,i,cost,k;
    scanf ("%d%d",&n,&m);
    for(i=1;i<=m;i++) {
        scanf ("%d%d%d",&x,&y,&cost);
        v[i].u=x;
        v[i].v=y;
        v[i].c=cost;
    }
    sort(v+1,v+m+1,cmp);
    for (i=1;i<=n;i++){
        t[i]=i;
        h[i]=1;
    }
    cost=0;
    i=1;k=0;
    while (k<n-1)
    {
        if(unionset(v[i].u,v[i].v)==1) {
            cost+=v[i].c;
            k++;
            sol[k]=i;
        }
        i++;
    }
    printf ("%d\n",cost);
    printf ("%d\n", n-1);
    for (i=1;i<=n-1;i++)
        printf("%d %d\n",v[sol[i]].u,v[sol[i]].v);
    return 0;
}