#define MAX_DEF_N 200000
#define _CRT_SECURE_NO_WARNINGS
#include<vector>
#include<algorithm>
using namespace std;

struct muchie{
	int x,y,cost;
};

struct selectata{ 
	int x,y;
};

bool func(muchie x, muchie y) { return (x.cost < y.cost); } 

void citire(vector<muchie> &muchiile, int &n){
	FILE *f = fopen("apm.in", "r");
	int m;
	fscanf(f, "%d%d", &n, &m);
	for (int i = 0, x, y, cost; i < m; i++){
		fscanf(f, "%d%d%d", &x, &y, &cost);
		muchie noua;
		noua.x = x; noua.y = y; noua.cost = cost;
		muchiile.push_back(noua);
	}
	sort(muchiile.begin(), muchiile.end(), func);
	fclose(f);
}

void kruskal(int tati[], vector<muchie> &muchiile, int &n, vector<selectata> &arb){
	for (int i = 0; i < (int) muchiile.size(); i++){
		
		int x = muchiile[i].x;
		int y = muchiile[i].y;
		int cost = muchiile[i].cost;

		//verific daca nu formeaza cilcu ... adica daca x si y nu au aceeasi radacina SAU in drumul lui x spre radacina intalnim pe y sau invers
		bool ok = false;
		int radx = tati[x], index = x, rady = tati[y];
		while (radx != index){
			if (radx == y) { ok = true; break; }
			index = radx;
			radx = tati[index];
		}
		if (!ok){
			index = y;
			while (rady != index){
				if (rady == x) { ok = true; break; }
				index = rady;
				rady = tati[index];
			}
		}
		// daca nu e ciclu inroduc muchia
		if (!ok && radx != rady) {			
			tati[0] += muchiile[i].cost;
			selectata noua; noua.x = x; noua.y = y; arb.push_back(noua);
			if (radx == x) tati[x] = y;
			else if (rady == y) tati[y] = x;
			else {
				tati[tati[y]] = y;
				tati[y] = x;
			}
		}
	}
}

void afisare(vector<muchie> &muchiile, int &sum, vector<selectata> &arb){
	FILE * f = fopen("apm.out", "w");
	fprintf(f, "%d\n", sum); 
	fprintf(f, "%d\n", (int)arb.size());
	for (int i = 0; i < (int)arb.size(); i++) fprintf(f, "%d %d\n", arb[i].y, arb[i].x);
	fclose(f);
}

int main(){
	vector <muchie> muchiile; int n;
	citire(muchiile, n);
	int tati[MAX_DEF_N];
	for (int i = 0; i <= n; i++) tati[i] = i;
	vector <selectata> arb;
	kruskal(tati, muchiile, n, arb);
	afisare(muchiile, tati[0], arb);
	return 0;
}