#include<fstream>
#include<algorithm>
using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

int w[200001],i,n,m,j,t,s,k;

struct muchie
{
    int x,y,c;
} v[200001],z[200001];

int fcomp(const void *x, const void *y)
{
    muchie a=*((muchie *)x);
    muchie b=*((muchie *)y);
    return a.c-b.c;
}
int main()
{
    f >> n >> m;
    int nr=0;
    for(i=1; i<=m; i++)
        f >> v[i].x >> v[i].y >> v[i].c;

    qsort(v+1,m,sizeof(muchie),fcomp);

    for(i=1; i<=n; i++)
        w[i]=i;
    k=1;
    for(i=1; i<n; i++)
    {
        while( w[ v[k].x ] == w[ v[k].y ] )
            k++;
        t=w[v[k].y];
        for(j=1; j<=n; j++)
            if(w[j]==t)
                w[j] = w[ v[k].x ];

        z[i].x = v[k].x;
        z[i].y = v[k].y;
        s += v[k].c;
        nr++;
    }

    g << s << "\n";
    g << nr << "\n";
    for(i=1; i<n; i++)
        g<< z[i].x << " " << z[i].y << "\n";
    return 0;
}