#include <cstdio>
#include <algorithm>
using namespace std;
int i,x,y,n,m,c,poz[400007],k,j,cost,aa[400007],bb[400007],aux,x1,y1,nr,h[400007];

struct nod
{
    int x, y, c;
} a[400007];

bool cmp ( nod a, nod b )
{
    if(a.c > b.c) return 0;
    return 1;
}

int tata(int x)
{
    if(poz[x]!=x) poz[x]=tata(poz[x]);
    return poz[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", &x, &y, &c);
        a[i].x = x;
        a[i].y = y;
        a[i].c = c;
    }
    sort (a+1, a+1+m, cmp);
    /*for (i=1; i<=m; i++)
    {
        printf("%d %d %d\n",a[i].x, a[i].y, a[i].c);
    }*/
    for (i=1; i<=m; i++)
        poz[i]=i;
    nr=0;
    for( i=1; i<=m; i++)
    {
        x1=tata(a[i].x);
        y1=tata(a[i].y);
        if(x1!=y1)
        {
            if(x1<y1) poz[x1]=y1;
            else poz[y1]=x1;
            if(x1==y1) y1++;
            k++;
            aa[k]=x1;
            bb[k]=y1;
            cost=cost+a[i].c;
            if(nr==n-1) break;
        }
    }
    printf("%d\n%d\n",cost,k);
    for(i=1;i<=k;i++)
    {
        printf("%d %d\n",aa[i], bb[i]);
    }
    return 0;
}