#include <cstdio>
#include <algorithm>
using namespace std;
#define MAX 200002

struct muchie{ int x,y,c; }u[2*MAX];
int rad[MAX],n,m;
bool was[MAX];

bool sort_mode(muchie a,muchie b){ return a.c < b.c; }

int tata(int x){
    if( x != rad[x] ) rad[x] = tata( rad[x] );
    return rad[x];
}

void apm(){
    sort(u,u+m,sort_mode);
   // for(int i=0;i<m;i++) printf("%d %d %d\n",u[i].x,u[i].y,u[i].c);
   for(int i=1;i<=n;i++) rad[i] = i;

   int i = 0, cost = 0;
   for(int k=1;k<n;k++)
   {
        while(tata( u[i].x ) == tata(u[i].y))i++;
        was[i] = 1;
        cost += u[i].c;
        rad[ tata(u[i].x) ] = tata(u[i].y);
        i++;
   }
   printf("%d\n",cost);
   printf("%d\n",n-1);
   for(int i=0;i<m;i++)
   if( was[i] ) printf("%d %d\n",u[i].x,u[i].y);
}

int main(){
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
        scanf("%d %d",&n,&m);
        for(int i=0;i<m;i++) scanf("%d %d %d",&u[i].x,&u[i].y,&u[i].c);

    apm();
    return 0;
}