#include<cstdio>
#include<algorithm>
#define N 200001
using namespace std;
int d[N],x[2*N],y[2*N],c[2*N],n,m,e,p[2*N],l[N],j=-1,i;
int M(int x)
{
    if(d[x]==x)
        return x;
    d[x]=M(d[x]);
    return d[x];
}
void R(int x,int y)
{
    d[M(x)]=M(y);
}
int F(int a,int b)
{
    return c[a]-c[b];
}
int main()
{
    freopen("apm.in","r",stdin),freopen("apm.out","w",stdout),scanf("%d%d",&n,&m);
    for(i=0;i<m;i++)
        scanf("%d%d%d",x+i,y+i,c+i),d[i]=p[i]=i;
    for(sort(p,p+m,F),i=0;i<m;++i)
        if(M(x[p[i]])!=M(y[p[i]]))
            e+=c[p[i]],R(x[p[i]],y[p[i]]),l[++j]=p[i];
    printf("%d\n%d\n",e,n-1);
    for(i=0;i<n-1;i++)
        printf("%d %d\n",x[l[i]],y[l[i]]);
}