#include <cstdio>
#include <algorithm>
#define mmax 400010
#define nmax 200010

using namespace std;

struct muchie
{
    int x,y,c;
}a[mmax];

int n,m,cost,sol[nmax],tata[nmax],h[nmax],k;

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

void citire()
{
    int i;
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++)
        scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].c);
    for(i=1;i<=n;i++)
        {
            tata[i]=i;
            h[i]=0;
        }
}

int radacina(int x)
{
    int rx=x;
    while(tata[rx]!=rx)
          rx=tata[rx];
    while(tata[x]!=x)
          {
              int aux=tata[x];
              tata[x]=rx;
              x=aux;
          }
    return rx;
}

void reuniune(int x, int y)
{
    int rx=radacina(x),ry=radacina(y);
    if(h[ry]>h[rx])
       tata[rx]=ry;
    else
        {
            tata[ry]=rx;
            if(h[rx]==h[ry])
               h[rx]++;
        }
}

void APM()
{
    int i;
    muchie m;
    for(i=1;k<n-1;i++)
        {
            m=a[i];
            if(radacina(m.x)!=radacina(m.y))
               {
                   cost+=m.c;
                   reuniune(m.x,m.y);
                   sol[++k]=i;
               }
        }
}

void afisare()
{
    int i;
    printf("%d\n%d\n",cost,k);
    for(i=1;i<=k;i++)
        printf("%d %d\n",a[sol[i]].y,a[sol[i]].x);
}

int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);

    citire();
    sort(a+1,a+m+1,cmp);
    APM();
    afisare();

    return 0;
}