#include <bits/stdc++.h>

using namespace std;

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

int n,m,cost,l[200005],k,x1,x2,sol[200005],i,j;

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

int comp (muchie a,muchie b)
{
    return a.c<b.c;
}

int main()
{
    f>>n>>m;
    for (i=1;i<=m;i++)
        f>>v[i].x>>v[i].y>>v[i].c;

    sort (v+1,v+m+1,comp);

    for (i=1;i<=n;i++) l[i]=i;

    i=1;
    while (k<=n-1)
    {
        x1=l[v[i].x];
        x2=l[v[i].y];

        if (x1!=x2) {

            cost+=v[i].c;
            k++;
            sol[k]=i;
            for (j=1;j<=n;j++)
                if (l[j]==x2) l[j]=x1;


        }
        i++;
    }


    g<<cost<<'\n'<<k<<'\n';
    for (i=1;i<=k;i++)
        g<<v[sol[i]].x<<" "<<v[sol[i]].y<<'\n';

    return 0;
}