#include<fstream>
#include<cstdlib>
#define W 200001
using namespace std;
int d[W],X[2*W],Y[2*W],C[2*W],N,m,c,p[2*W],l[W],n=-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(const void *a, const void *b)
{
    return C[*(int *)a]-C[*(int *)b];
}
int main()
{
    ifstream f("apm.in");
    ofstream g("apm.out");
    f>>N>>m;
    for(i=0;i<m;++i)
    {
        f>>X[i]>>Y[i]>>C[i];
        d[i]=p[i]=i;
    }
    qsort((void *)p,M,sizeof(p[0]),F);
    for(i=0;i<m;++i)
        if(M(X[p[i]])!=M(Y[p[i]]))
        {
            c+=C[p[i]];
            R(X[p[i]],Y[p[i]]);
            l[++n]=p[i];
        }
    g<<c<<'\n'<<N-1<<'\n';
    for(i=0;i<N-1;++i)
        g<<X[l[i]]<<' '<<Y[l[i]]<<'\n';
}