#include <iostream>

#include <stdio.h>

using namespace std;

struct muchie{int st, dr, cost;};

muchie M[400001];
bool viz[200001];
int cost,rada[200001],n,loc;

void read()
{ int x,y , c;
    freopen ( "apm.in","r",stdin);
    int m;
    scanf("%d%d",&n,&m);

    for ( int i =1 ; i <= m ; ++i)
    {
        scanf("%d%d%d",&x,&y,&c);
++loc;
M[loc].st=x;
M[loc].dr=y;
M[loc].cost=c;
    }
    for ( int i = 1 ; i<= n  ; ++i)
        rada[i]=i;
}

void ordonare()
{
    int i,j;

    for ( i = 1 ; i <loc ; ++i)
        for( j = i + 1 ; j <= loc ; ++j)
        if(M[i].cost>M[j].cost)swap(M[i],M[j]);

}




int main()
{

    read();
    ordonare();




int nr=0;

for ( int i = 1 ; i <= loc && nr<n ; ++i)
{

    if(rada[M[i].st] != rada[M[i].dr])

{
    viz[i]=1;

    cost+=M[i].cost;

 nr ++;

    int stanga=rada[M[i].st]; int dreapta=rada[M[i].dr];

    for ( int p = 1 ; p <= loc ; ++p)
        if(rada[p]==dreapta)rada[p]=stanga;

}
}

freopen("apm.out","w",stdout);
printf("%d\n",cost);
printf("%d\n",nr);

for ( int i = 1 ; i <= loc ; ++i)
    if(viz[i])
{
    printf("%d %d\n",M[i].st,M[i].dr);

}



    return 0;
}