#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
int l[200005],n,m,i,k,cost,j,p1,p2;
struct much
{
    int x,y,c;
};
bool acompare(much x1,much y1)
{
    return x1.c<y1.c;
}
much u[400001],sol[400001];
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",&u[i].x,&u[i].y,&u[i].c);
        l[i]=i;
    }

    sort(u+1,u+m+1,acompare);

    k=0;
    cost=0;
    i=1;
    while(k<n-1)
    {
        if(l[u[i].x]!=l[u[i].y])
        {
            k++;
            sol[k]=u[i];
            cost+=u[i].c;
            p1=l[u[i].x];
            p2=l[u[i].y];
            for(j=1;j<=n;j++)
            {
                if(l[j]==p2)
                    l[j]=p1;
            }
        }
        i++;
    }

    printf("%d\n",cost);
    printf("%d\n",k);
    for(i=1;i<=k;i++)
    {
        printf("%d %d\n",u[i].x,u[i].y);
    }


    return 0;
}