#include<cstdio>
#include<algorithm>
using namespace std;
FILE *fin=fopen("amp.in","r");
FILE *fout=fopen("amp.out","w");
int n,m,x,y,c,v[200003],minn,maxx,i,j,cost;
struct aaa
{
    int x,y,c,ok;
}muchie[200003];

int cmp(aaa a,aaa b) {return a.c<b.c;}
int main()
{
    fscanf(fin,"%d%d",&n,&m);
    for(i=1;i<=m;++i)
        fscanf(fin,"%d%d%d",&muchie[i].x,&muchie[i].y,&muchie[i].c);
    for(i=1;i<=n;++i)
        v[i]=i;
    sort(muchie+1,muchie+m+1,cmp);
    for(i=1;i<=m;++i)
    {
        if(v[muchie[i].x]!=v[muchie[i].y])
        {
            cost+=muchie[i].c;
            minn=min(v[muchie[i].x],v[muchie[i].y]);
            maxx=max(v[muchie[i].x],v[muchie[i].y]);
            for(j=1;j<=n;++j)
                if(v[j]==maxx)
                {
                    v[j]=minn;
                }
            muchie[i].ok=1;
        }
    }
    fprintf(fout,"%d\n%d\n",cost,n-1);
    for(i=1;i<=m;++i)
        if(muchie[i].ok)
            fprintf(fout,"%d %d\n",muchie[i].y,muchie[i].x);
    return 0;
}