#include <cstdio>
#include<algorithm>
int i,n,m,q,qq,nr,l,s,w;
short v[400004],ww[200005],www[200005];
using namespace std;
struct andreea
{
    short n1,n2,val;
}a[200005];
bool cmp(andreea a, andreea b)
{
    if(a.val>b.val)return 0;
    return 1;
}
int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    scanf("%d%d",&nr,&n);
    for(i=1;i<=n;i++)
    {
        scanf("%hd%hd%hd",&a[i].n1,&a[i].n2,&a[i].val);
    }
    sort(a+1,a+n+1,cmp);
    //pana aici e bine
    for(i=1;i<=nr;i++)
    {
        v[i]=i;
    }
    for(l=1;l<=n;l++)
    {
        if(v[a[l].n1]!=v[a[l].n2])
        {
            q=v[a[l].n1];
            qq=v[a[l].n2];
            for(i=1;i<=nr;i++)
            {
                if(v[i]==qq)v[i]=q;
            }
            s=s+a[l].val;
            w++;
            ww[w]=a[l].n1;
            www[w]=a[l].n2;
        }
    }
    printf("%d\n%d\n",s,w);
    for(i=1;i<=w;i++)
    {
        printf("%d %d\n",www[i],ww[i]);
    }
    return 0;
}