#include <cstdio>
#include <algorithm>
using namespace std;
int i,x,y,n,m,c,poz[400007],k,j,cost,aa[400007],bb[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 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;
    for( i=1; i<=m; i++)
    {
        x = a[i].x;
        y = a[i].y;
        c = a[i].c;
        if( poz[x] != poz[y])
        {
            k++;
            aa[k]=x;
            bb[k]=y;
            for(j=1; j<=n; j++)
            {
                if(poz[j]==poz[x])  poz[j]=poz[y];
            }
            cost+=c;
        }
        if(k==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;
}