#include <stdio.h>
#include <algorithm>

#define Nmax 200005
#define Mmax 400005

using namespace std;

int n, m, i, j, cost, a, b, c, d, nr, w, q;
int vizM[Mmax], padure[Nmax], rang[Nmax];
struct apm{
	int x, y, c;
} v[Mmax];

int cmp (apm a, apm b){
	if (a.c < b.c)
		return 1;
	return 0;
}


int main (){
	freopen ("apm.in", "r", stdin);
	freopen ("apm.out", "w", stdout);
	
	scanf("%d %d", &n, &m);
	
	for (i = 1 ; i <= n ; i++)
		padure[i] = i;
	
	for (i = 1 ; i <= m ; i++)
		scanf("%d %d %d", &v[i].x, &v[i].y, &v[i].c);
	
	sort(v+1,v+m+1,cmp);
	
	for (i = 1 ; i <= m ; i++){
		a = v[i].x;
		
		while (a != padure[a]){
			a = padure[a];
		}
		
		q = v[i].x;
		
		while (q != padure[q]){
			b = padure[q];
			padure[q] = a;
			q = b;
		}
			
		c = v[i].y;
		
		while (c != padure[c]){
			c = padure[c];
		}
		
		w = v[i].y;
		
		while (w != padure[w]){
			d = padure[w];
			padure[w] = c;
			w = d;
		}
		
		
		
		if (a != c){
			if (rang[ padure[v[i].x] ] < rang[ padure[v[i].y] ]){
				a = v[i].x;
				while (a != padure[a]){
					a = padure[a];
				}
				
				c = v[i].y;
				while (c != padure[c]){
					c = padure[c];
				}
				
				padure[a] = padure[c];
				rang[c]++;
			}
			else{
				a = v[i].x;
				while (a != padure[a]){
					a = padure[a];
				}
				
				c = v[i].y;
				while (c != padure[c]){
					c = padure[c];
				}
				
				padure[c]=padure[a];
				rang[a]++;
			}
			
			
			cost += v[i].c;
			vizM[i]++;
			nr++;
		}
		
	}
	
	printf ("%d\n%d\n", cost, nr);
	for (i = 1 ; i<= m ; i++)
		if (vizM[i]) 
			printf ("%d %d\n", v[i].x, v[i].y);
	
	return 0;
}