#include<fstream>
#include<cstdlib>
using namespace std;
int d[200001],x[400001],y[400001],c[400001],n,m,e,p[400001],l[200001],i,j;
int mult(int x)
{
    if(d[x]==x)
        return x;
    d[x]=mult(d[x]);
    return d[x];
}
void reun(int x,int y)
{
    d[mult(x)]=mult(y);
}
int fs(const void *a,const void *b)
{
    return c[*(int*)a]-c[*(int*)b];
}
int main()
{
    ifstream f("apm.in");
    ofstream g("apm.out");
    for(f>>n>>m,i=0;i<m;i++)
        f>>x[i]>>y[i]>>c[i],d[i]=p[i]=i;
    qsort((void*)p,m,sizeof(p[0]),fs);
    for(i=0;i<m;i++)
        if(mult(x[p[i]])!=mult(y[p[i]]))
        {
            e+=c[p[i]];
            reun(x[p[i]],y[p[i]]);
            l[j++]=p[i];
        }
    g<<e<<'\n'<<n-1<<'\n';
    for(i=0;i<n-1;++i)
        g<<x[l[i]]<<' '<<y[l[i]]<<'\n';
}