#include <cstdio>
#include <algorithm>


using namespace std;

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

int n,m,cost,v[200002],t[200002],h[200002],k;

int cond(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++)
    {
        t[i]=i;
        h[i]=0;
    }
}

int rad(int x)
{
    int aux=x;
    while(t[aux]!=aux)
          aux=t[aux];
    while(t[x]!=x)
          {
              int aux2=t[x];
              t[x]=aux;
              x=aux2;
          }
    return aux;
}

void reunion(int x, int y)
{
    int aux=rad(x),aux2=rad(y);
    if(h[aux2]>h[aux])
       t[aux]=aux2;
    else
        {
            t[aux2]=aux;
            if(h[aux]==h[aux2])
               h[aux]++;
        }
}

void part()
{
    int i;
    muchie aux;
    k=1;
    for(i=1;k<=n-1;i++)
        {
            aux=a[i];
            if(rad(aux.x)!=rad(aux.y))
               {
                   cost+=aux.c;
                   reunion(aux.x,aux.y);
                   v[k]=i;
                   k++;
               }
        }
    k--;
}

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

int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    citire();
    sort(a+1,a+m+1,cond);
    part();
    afisare();
    return 0;
}