#include<stdio.h>
	#define MAX 200001
	FILE *f , *g ;
	struct {
		int x , y , c ;
		bool d;
	}a[MAX], aux1, aux[MAX] ;
	int n , m , much , rang[MAX] , point[MAX] , cost ;
	
	void citire();
	void sort(int x , int y);
	void kruskal();
	int find(int x);
	void reun(int x , int y);
	void tipar();
	void swap(int i , int j);
	
	int main()
	{
		citire();
		sort(1,m);
		/*int h , sw ;
	h = m;
	while(h > 1)
	{
		h/=2;
		do
		{
			sw = 0;
			for( int i = 1 ; i<= m-h ; ++i )
				if(a[i].c > a[i+h].c)
				{
					swap(i,i+h);
					sw = 1;
				}
		}while(sw);
	}*/
		kruskal();
		tipar();
		return 0;
	}
	
	void citire()
	{
		f=fopen("apm.in" , "r" );
		fscanf(f , "%d%d" , &n , &m );
		for( int i = 1 ; i<= m ; ++i )
			fscanf(f , "%d%d%d" , &a[i].x , &a[i].y , &a[i].c );
		fclose(f);
	}
	
	void sort(int x , int y)
	{
		if(x == y)
			return;
		sort(x,(x+y)/2);
		sort((x+y)/2+1 , y);
		int au = x;
		int b = (x+y)/2+1;
		int k = 0;
		while(au <= (x+y)/2 && b <= y)
		if(a[au].c < a[b].c)
		{
			aux[++k] = a[au];
			au++;
		}
		else
		{
			aux[++k] = a[b];
			b++;
		}
		while(au <= (x+y)/2)
			aux[++k] = a[au++];
		while(b <= y)
			aux[++k] = a[b++];
		au = 1;
		for(int i = x ; i<= y ; ++i )
			a[i] = aux[au++];
	}
	
	void swap(int i , int j )
	{
		aux1 = a[i];
		a[i] = a[j];
		a[j] = aux1;
	}
	
	void kruskal()
	{
		for( int i = 1 ; i<= n ; ++i )
		{
			rang[i] = 1;
			point[i] = i;
		}
		int k = 1;
		while(much < n-1 )
		{
			if(find(a[k].x) != find(a[k].y))
			{
				reun(find(a[k].x),find(a[k].y));
				cost+=a[k].c;
				a[k].d = 1;
				much ++ ;
			}
			k++;
		}
	}
	
	int find(int x)
	{
		int aux , aux1;
		aux = point[x];
		while(aux != point[aux])
			aux = point[aux];
		while(x != point[x])
		{
			aux1 = point[x];
			point[x] = aux;
			x = aux1;
		}
		return aux;
	}
	
	void reun( int x , int y)
	{
		if(rang[x] > rang[y])
			point[y] = x;
		else
			point[x] = point[y];
		if(rang[x] == rang[y])
			rang[y]++;
	}
	
	void tipar()
	{
		g=fopen("apm.out" , "w" );
		/*for( int i = 1 ; i<= m ; ++i )
			fprintf(g , "%d %d %d\n" , a[i].x , a[i].y , a[i].c );*/
		fprintf(g , "%d\n%d\n" , cost , much);
		for( int i = 1 ; i<= m ; ++i )
			if(a[i].d)
				fprintf(g , "%d %d\n" , a[i].x , a[i].y );
		fclose(g);
	}