#include<cstdio>
#include<vector>
#include<algorithm>
#define f first
#define s second
const int maxn = 200005;
using namespace std;

int i , j , n , m , a , b , c, rang[maxn] , dad[maxn] , sol[maxn];
struct edge { int x , y , cost;} edges[maxn * 2];
struct cmp { bool operator () ( const edge &A , const edge &B ) { return (A.cost < B.cost);}};

int find( int A ) {
	int root , x;
	
	for( root = A ; root != dad[root] ; root = dad[root]);
	for(  ; A != root ;) {
		int aux = dad[A];
		dad[A] = root;
		A = aux;
	}
return root;
}

void join ( int A , int B ) {
	dad[A] = B;
}

void Kruskal()
{
	int i , ans = 0, k = 0;
	
	for( i = 1 ; i <= m && k < n - 1 ; ++i ) {
		if (  find( edges[i].x ) != find( edges[i].y ) ) {
				join ( edges[i].x, edges[i].y);
				ans += edges[i].cost;
				sol[++k] = i;
		}
	}
	
	printf("%d\n",ans);
	printf("%d\n",n - 1);
	for( i = 1 ; i <= k ; ++i ) 
		printf("%d %d\n",edges[sol[i]].x, edges[sol[i]].y);
	
}

int main()
{
	freopen("apm.in","r",stdin);
	freopen("apm.out","w",stdout);
	
	scanf("%d %d",&n,&m);

	for( i = 1 ; i <= m ; ++i ) {
		scanf("%d %d %d",&a,&b,&c);
		edges[i].x = a , edges[i].y = b, edges[i].cost = c;
	}
	for ( i = 1 ; i <= n ; ++i )
		dad[i] = i , rang[i] = 1;
	
	sort ( edges + 1 , edges + m + 1 , cmp() );
	
	Kruskal();
	
return 0;
}