#include <cstdio>
#include <algorithm>

using namespace std;

struct edge
{
    int x,y,c;
}v[400010];

int rad[200010],rez[200010];

int cmp(edge a,edge b)
{
    return a.c<b.c;
}

int radacina(int x)
{
    int y=x;
    while(y!=rad[y]) y=rad[y];
    while(x!=y)
    {
        int aux=rad[x];
        rad[x]=y;
        x=aux;
    }
    return y;
}

void reuneste(int a,int b)
{
    a=radacina(a);b=radacina(b);
    rad[a]=b;
}

int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    int n,m,sol=0,l=0;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++) scanf("%d%d%d",&v[i].x,&v[i].y,&v[i].c);
    sort(v+1,v+m+1,cmp);
    for(int i=1;i<=n;i++) rad[i]=i;
    for(int i=1;i<=m;i++)
        if(radacina(v[i].x)!=radacina(v[i].y))
        {
            rez[++l]=i;
            reuneste(v[i].x,v[i].y);
            sol+=v[i].c;
            if(l==n-1) break;
        }
    printf("%d\n%d\n",sol,l);
    for(int i=1;i<=l;i++) printf("%d %d\n",v[rez[i]].x,v[rez[i]].y);
    return 0;
}