#include <stdio.h>
#include <algorithm>
#define max 400010

using namespace std;

int rang[max],d[max],x[max],y[max],tata[max],ind[max],sol[max],n,m,i,j,cost,k;
int find(int x)
{
     if(tata[x]==x) return x;
     tata[x]=find(tata[x]);
     return tata[x];
}
void unite(int x,int y)
{
    tata[find(x)]=find(y);
}

bool cmp(int i,int j)
{
    return (d[i]<d[j]);
}
int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.in","w",stdout);
    scanf("%d%d",&n,&m);
    for(i=1; i<=m; i++)
    {
        scanf("%d%d%d",&x[i],&y[i],&d[i]);
        ind[i]=i;
    }
    for(i=1; i<=n; i++) tata[i]=i;
    sort(ind+1,ind+m+1,cmp);
    for(i=1; i<=m; i++)
     if(find(x[ind[i]])!=find(y[ind[i]]))
     {
         cost+=d[ind[i]];
         unite(x[ind[i]],y[ind[i]]);
         sol[++k]=ind[i];
     }

    printf("%d\n",cost);
    printf("%d\n",n-1);
    for(i=1; i<=k; i++)
     printf("%d %d\n",x[sol[i]],y[sol[i]]);
    return 0;
}