#define test 
#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);
}

int rad(int x, int tati[]){
	int r = x;
	for (; tati[r] != r; r = tati[r]);
	for (int k = x, t; tati[k] != r; t = k, k = tati[k], tati[t] = r);
	return r;
}

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
		int radx = tati[x], index = x, rady = tati[y];

		// daca nu e ciclu inroduc muchia
		if (rad(x, tati) != rad(y, tati)) {			
			tati[0] += cost;
			selectata noua; noua.x = x; noua.y = y; arb.push_back(noua);
			tati[tati[x]] = tati[tati[y]];
		}
	}
}

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;
}