#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

struct muchie {
	int nod1, nod2, cost;
};

bool cmp(const muchie& a, const muchie& b) {
	return a.cost < b.cost;
}

vector <int> vect_tati;
vector <int> vect_h;
vector <muchie> vect_muchii;
vector <int> vect_ans;

int get(int);  // cauta grupa
void unite(int, int);  // adauga la grupa(muchie intre ele)

int main(void) {
	int n, m, ans = 0;
	freopen("apm.in", "r", stdin);
	scanf("%d %d", &n, &m);
	
	vect_muchii.resize(m);
	vect_tati.resize(n + 1);
	vect_h.resize(n + 1);
	int a, b, c;
	for(int i = 0; i < m; ++i) {
		scanf("%d %d %d", &a, &b, &c);
		vect_muchii[i].nod1 = a;
		vect_muchii[i].nod2 = b;
		vect_muchii[i].cost = c;
	}
	
	for(int i = 0; i <= n; ++i) {
		vect_tati[i] = i;
		vect_h[i] = 1;
	}
	 
	sort(vect_muchii.begin(), vect_muchii.end(), cmp);
	for(int i = 0; i < m; ++i)
		if(get(vect_muchii[i].nod1) != get(vect_muchii[i].nod2)) {
			ans += vect_muchii[i].cost;
			vect_ans.push_back(vect_muchii[i].nod1);
			vect_ans.push_back(vect_muchii[i].nod2);
			unite(vect_muchii[i].nod1, vect_muchii[i].nod2);
		}
	
	freopen("apm.out", "w", stdout);
	printf("%d\n%d\n", ans, vect_ans.size() / 2);
	for(int i = 0; i < (int)vect_ans.size(); ++i) {
		printf("%d ", vect_ans[i]);
		if(i % 2 == 1)
			printf("\n");
	}
}

int get(int x) {
	if(vect_tati[x] == x)
		return x;
	vect_tati[x] = get(vect_tati[x]);
	return vect_tati[x];
}

void unite(int x, int y) {
	int a = get(x);
	int b = get(y);
	if(vect_h[a]  < vect_h[b]) 
		vect_tati[a] = b;
	else if(vect_h[a] >= vect_h[b]) {
		vect_tati[b] = a; 
		if(vect_h[a] == vect_h[b])
			vect_h[a] = vect_h[a] + 1;
	}
}