#include <stdio.h>
#include <string.h>
#include <queue>

using namespace std;

struct muchie
{
    int x,y,c;
}v[400005],vc[400005];
int vin[400005];

int t[200005],r[200005];
unsigned int sm;

void swag2(muchie &a, muchie &b)
{
    muchie aux;
    memcpy(&aux,&a,sm);
    memcpy(&a,&b,sm);
    memcpy(&b,&aux,sm);
}

void swag(int &a, int &b)
{
    int aux;
    aux=a;
    a=b;
    b=aux;
}

void heapup(int x)
{
    int i=x,j;
    while(i>1)
    {
        j=i/2;
        if(v[vin[j]].c<v[vin[i]].c)
        {
            swag(vin[i],vin[j]);i=j;
        }
        else break;
    }
}

void heapdown(int &ncr)
{
    int i,j,x;
    swag(vin[1],vin[ncr]);
    ncr--;
    i=1;
    while(2*i<=ncr)
    {
        j=2*i;
        if(j+1<=ncr&&v[vin[j]].c<v[vin[j+1]].c) j++;
        if(v[vin[i]].c<v[vin[j]].c) {swag(vin[i],vin[j]);i=j;}
        else break;
    }
}

void heapsort(int n)
{
    int i,j,ncr=n;
    sm=sizeof(muchie);
    vin[1]=1;
    for(i=2;i<=n;i++)
    {
        vin[i]=i;
        heapup(i);
    }
    for(i=n;i>=1;i--)
    {
        memcpy(&(vc[i]),&(v[vin[1]]),sm);
        heapdown(ncr);
    }
}

void uneste(int x, int y)
{
    t[y]=x;
}

int query(int x)
{
    int rad=x,aux;
    while(rad!=t[rad])
        rad=t[rad];

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

    return rad;
}

int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    int n,m,i,narb,narbc=0,x,y,a,b,cost=0;
    queue<int> q;
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++)
    {
        scanf("%d%d%d",&(v[i].x),&(v[i].y),&(v[i].c));
    }
    heapsort(m);

    for(i=1;i<=n;i++)
        t[i]=i;

    narb=n-1;
    for(i=1;i<=m&&narbc<narb;i++)
    {
        x=vc[i].x;
        y=vc[i].y;
        a=query(x);
        b=query(y);
        if(a==b) continue;

        if(r[a]>=r[b])
            uneste(a,b);
        else uneste(b,a);
        if(r[a]==r[b]) r[a]++;
        cost+=vc[i].c;
        q.push(i);
        narbc++;
    }
    printf("%d\n%d\n",cost,narb);
    while(!q.empty())
    {
        printf("%d %d\n",vc[q.front()].x,vc[q.front()].y);
        q.pop();
    }

    return 0;
}