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

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

struct selectata{
	int x,y;
};

bool func(muchie A, muchie B) {return (A.cost > B.cost);}

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

void prim(vector<muchie> &E, int n, int &sum, vector<selectata> &arb, bool V[]){
	int nr = 1;
	V[1]++;
	while (nr != n){
		for (int i = (int) E.size() - 1; i >= 0; i--) 
			if (!E[i].used)
				if ((V[E[i].x] && !V[E[i].y]) || (V[E[i].y] && !V[E[i].x])){
					selectata noua; 
					noua.x = E[i].x;
					noua.y = E[i].y;
					arb.push_back(noua);
					E[i].used = V[E[i].x] = V[E[i].y] = 1;
					nr++;
					sum += E[i].cost;
					if (E[(int)E.size() - 1].used) E.pop_back();
					break;
				}

	}
}


void afisare(vector<selectata> &arb, int &sum){
	FILE *f = fopen("apm.out", "w");
	fprintf(f, "%d\n%d\n", sum, (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> E;
	int n;
	citire(E, n);
	vector<selectata> arb; 
	int sum = 0;
	bool V[NMAX]; memset(V, 0, sizeof(V));
	prim(E, n, sum, arb, V);
	afisare(arb, sum);
	return 0;
}