#include<fstream>
#define N 200001
#define in "apm.in"
#define out "apm.out"
#define max 1<<30

using namespace std;

struct nod{
	
	int catre;
	int cost;
	nod* urm;
};

nod *G  [N]; 
int C   [N]; 
int P   [N]; 
int Poz [N];
int Heap[N]; 
char viz[N];
int dim_heap,n,m,nr;

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

void init(){
	
	int i;
	for(i=1;i<=n;i++) { C[i] = max; Poz[i] = -1 ; }

	C[1] = 0;
	Heap[1] = 1;
	Poz [1] = 1;
	dim_heap= 1;
	nr = n-1;
	
}

void down_heap( int poz ){
	
	int fiu_stang, fiu_drept;
	
	for( ;; ){
		
		fiu_stang = 2 * poz;
		if( fiu_stang > dim_heap ) return;
		fiu_drept = fiu_stang + 1;
		if( fiu_drept <= dim_heap && C[Heap[ fiu_drept ]] < C[Heap[fiu_stang]]) fiu_stang++;
		if( C[Heap[fiu_stang]] >= C[Heap[poz]] ) return;
		swap( Heap[poz] , Heap[fiu_stang]);
		Poz[Heap[poz]] = poz;
		Poz[Heap[fiu_stang]] = fiu_stang;
		poz=fiu_stang;
	}
}

void up_heap( int poz ){
	
	int tata=poz>>1;
	
	while( poz > 1 && C[Heap[poz]] < C[Heap[tata]]){
		
		swap( Heap[tata], Heap[poz]);
		Poz[Heap[tata]] = tata;
		Poz[Heap[poz]] = poz;
		poz = tata;
		tata>>=1;
	}
}

void add( int nd ){
	
	Heap[ ++ dim_heap ] = nd;
	Poz[ Heap[ dim_heap] ] = dim_heap;
	
	up_heap( dim_heap );
}

void rem( int poz ){
	
	swap( Heap[poz] , Heap[ dim_heap-- ] );
	Poz [ Heap[1] ] = 1;
		
	down_heap( 1 );
}

void apm(){
	
	init();
	int min;
	
	while ( nr ){
		
			min = Heap[1];
			viz[min]=1;
			rem(1);
			nr--;
			
			nod *q = new nod;
			q = G[min];
			
			
			for( ; q ; q = q->urm ) {
				
				if( !viz[q->catre] && C [ q->catre ] >=q -> cost ){
					P[ q->catre ] = min;
					C[ q->catre ] = q->cost;
					if( Poz[ q->catre ] == -1 ) add( q->catre );
					else up_heap( Poz [ q->catre ] );
				}
			}
	}
}

void ADD( nod *& L, int nd, int ct){
	
	nod *q = new nod;
	q->catre = nd;
	q->cost = ct;
	q->urm = L;
	L=q;
}

void print(){
	
	ofstream g(out);
	
	int i;
	int total=0;
	for(i=2;i<=n;i++) total += C[i];
	g<<total<<"\n"<<n-1<<'\n';
	for(i=2;i<=n;i++)g<<P[i]<<" "<<i<<'\n';
}
	
void data(){
	
	ifstream q(in);
	
	q>>n>>m;
	int x,y,c,i;
	
	for(i=1;i<=m;i++){
		q>>x>>y>>c;
		ADD( G[x], y, c);
		ADD( G[y], x, c);
	}
}

int main(){

		data() ;
		init() ;
		 apm() ; 
		print();
		
		return 0;
}