#define NMAX 200000
#define _CRT_SECURE_NO_WARNINGS
#include<vector>
#include<limits.h>
using namespace std;

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

struct selectata{
	int x,y;
};


void introdu(muchie *prim, muchie *noua){
	if (noua->cost < prim->cost){
		noua->urm = prim;
		prim = noua;
		return;
	}
	muchie *p = prim;
	while (noua->cost > p->urm->cost) p = p->urm;
	noua->urm = p->urm;
	p->urm = noua;
}

void citire(muchie *prim, int &n){
	FILE *f = fopen("apm.in", "r");
	int m;
	fscanf(f, "%d%d", &n, &m);
	prim = new muchie;
	prim->urm = NULL; prim->cost = LONG_MAX;
	for (int i = 0; i < m; i++){
		muchie *noua = new muchie;
		fscanf(f, "%d%d%d", &noua->x, &noua->x, &noua->cost);
		introdu(prim, noua);
	}
	fclose(f);
}

void algprim(muchie *prim, int n, int &sum, vector<selectata> &arb, bool V[]){
	int nr = 1;
	V[1]++;
	muchie *p = prim, *q;
	while (nr != n){
		p = prim;
		while (p->cost != LONG_MAX){
				if ((V[p->x] && !V[p->y]) || (V[p->y] && !V[p->x])){
					selectata noua; 
					noua.x = p->x;
					noua.y = p->y;
					arb.push_back(noua);
					V[p->x] = V[p->y] = 1;
					nr++;
					sum += p->cost;
					if (p == prim){
						prim = prim->urm;
						delete(p);
					}
					else {
						q->urm = p->urm;
						delete(p);
					}
					break;
				}
				q = p;
				p = p->urm;
		}
	}
}


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(){
	muchie *prim;
	int n;
	citire(prim, n);
	vector<selectata> arb; 
	int sum = 0;
	bool V[NMAX]; memset(V, 0, sizeof(V));
	algprim(prim, n, sum, arb, V);
	afisare(arb, sum);
	return 0;
}