#include<cstdio>
#include<algorithm>
using namespace std;
struct eu{int x,y,val;};
eu v[400001],vc[200001];
int parinti[200001],i,j,n,m,k,s,cate,fii[200001];
bool sorting(eu a,eu b)
    {
    return a.val<b.val;
    }
int find1(int nod)
    {
    int nod1=nod,x;
    while(parinti[nod1]!=nod1)
        nod1=parinti[nod1];
    x=nod1;
    nod1=nod;
    while(parinti[nod1]!=nod1)
        {
        int nod2=nod1;
        nod1=parinti[nod1];
        parinti[nod2]=x;
        }
    return x;
    }
void join(int nod1,int nod2)
    {
    int x=find1(nod1);
    int y=find1(nod2);
    if(fii[x]>fii[y])
        {
        parinti[y]=x;
        fii[x]+=fii[y];
        }
    else
        {
        parinti[x]=y;
        fii[y]+=x;
        }
    }
int main ()
{
freopen("apm.in","r",stdin);
freopen("apm.out","w",stdout);
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)
    {
    parinti[i]=i;
    fii[i]=1;
    }
for(i=1;i<=m;i++)
    scanf("%d%d%d",&v[i].x,&v[i].y,&v[i].val);
sort(v+1,v+m+1,sorting);
for(i=1;i<=m;i++)
    {
    int x=v[i].x;
    int y=v[i].y;
    if(find1(x)!=find1(y))
        {
        join(x,y);
        s+=v[i].val;
        cate++;
        vc[cate].x=x;
        vc[cate].y=y;
        }
    }
printf("%d\n",s);
printf("%d\n",n-1);
for(i=1;i<=cate;i++)
    printf("%d %d\n",vc[i].x,vc[i].y);
return 0;
}