#include <stdio.h>
#include <algorithm>
#include <vector>
#define MAX 200005
using namespace std;

typedef struct{
	int s, d;
} SimpleEdge;

typedef struct{
	int s, d, c;
} Edge;

bool compare(Edge a, Edge b){
	return a.c < b.c;
}

vector<Edge> v;
vector<int> l[MAX];
int set[MAX], size[MAX], i;

void MakeSet(int n);
int Find(int x);
void Union(int x, int y);

int main(){
	freopen("apm.in", "r", stdin);
	freopen("apm.out", "w", stdout);
	int n, m, x, y, z, cnt = 0, rez = 0;
	vector<SimpleEdge> a;
	Edge aux;
	SimpleEdge aux2;
	scanf("%d%d", &n, &m);
	for(i = 0; i < m; i++){
		scanf("%d%d%d", &x, &y, &z);
		aux.s = x;
		aux.d = y;
		aux.c = z;
		v.push_back(aux);
	}
	sort(v.begin(), v.end(), compare);
	MakeSet(n);

	for(i = 0; i < m; i++){
		aux = v[i];
		x = Find(aux.s);
	 	y = Find(aux.d);
		if(x != y){
			cnt++;
			rez += aux.c;
			aux2.s = aux.s;
			aux2.d = aux.d;
			a.push_back(aux2);
			Union(x, y);
		}
		if(cnt == n - 1)
			break;
	}

	printf("%d\n%d\n", rez, cnt);
	for(i = 0; i < n - 1; i++)
		printf("%d %d\n", a[i].s, a[i].d);

	return 0;
}

void MakeSet(int n){
	for(i = 1; i <= n; i++)
  	set[i] = i;
}

int Find(int x){
	int r = x;
	while(set[r] != r)
		r = set[r];

	while(x != set[x]){
		x = set[x];
		set[x] = r;
	}
	return r;
}

void Union(int x, int y){
	if(size[x] > size[y])
		set[y] = x;
	else
		set[x] = y;

	if(size[x] == size[y])
		size[y]++;
}