#include <cstdio>
#include <algorithm>

using namespace std;
struct muchie
{
    int x,y,c;
} a[400005];
int n,m,i,r1,r2,muchii,cost,solx[400005],t[200005];

bool cmp(muchie a, muchie b)
{
    return a.c<=b.c;
}

int tata(int x)
{
    while (x!=t[x])
        x=t[x];
    return x;
}

int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    scanf("%d%d",&n,&m);
    for (i=1; i<=m; i++)
        scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].c);
    sort(a+1,a+m+1,cmp);
    for (i=1; i<=n; i++)
        t[i]=i;
    for (i=1; i<=m; i++)
    {
        r1=tata(a[i].x);
        r2=tata(a[i].y);
        if (r1!=r2)
        {
            muchii++;
            solx[muchii]=i;
            cost=cost+a[i].c;
            t[r1]=r2;
        }
    }
    printf("%d\n%d\n",cost,muchii);
    for (i=1; i<=muchii; i++)
        printf("%d %d\n",a[solx[i]].x,a[solx[i]].y);
    return 0;
}