#include<fstream.h>
#include<stdlib.h>
#define NM 200001
#define MM 400001
#define endl "\n"

ifstream fin("apm.in");
ofstream fout("apm.out");

struct muchie{ int x,y,c;};

int n,m,L[NM];
muchie v[MM],h[NM];

void citire(){
     int i;
     fin>>n>>m;
     for(i=0;i<m;i++)
     fin>>v[i].x>>v[i].y>>v[i].c;
     }

int fcmp(void const*a,void const*b){
    return ((muchie*)a)->c-((muchie*)b)->c;
    }

int Min(int x,int y){
    if(x<y) return x;
    return y;
    }

int Max(int x,int y){
    if(x>y) return x;
	    return y;
	    }

int Find(int x){ if(x==L[x]) return x;
		 return Find(L[x]);
		 }

void Union(int x,int y){
     int px=Find(x);
     int py=Find(y);
     if(px<py) 	L[py]=px;
     else L[px]=py;
     }



int  main(){
     int i,ms=0,j,ct=0;
     citire();
     qsort(v,m,sizeof(v[0]),fcmp);
     for(i=1;i<=n;i++) L[i]=i;
     i=0;
     while(ms<n-1){
	   int px,py;
	   do{ px=Find(v[i].x);
	       py=Find(v[i].y);
	       if(px==py)i++;
	       }while(px==py);
	   h[ms]=v[i];
	   ms++;
	   ct+=v[i].c;
	   int a=Max(px,py);
	   int b=Min(px,py);
	   Union(b,a);
	   }
     fout<<ct<<endl<<n-1<<endl;
     for(i=0;i<n-1;i++)
     fout<<h[i].x<<" "<<h[i].y<<" "<<endl;
     return 0;
     }