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

struct muchie{
	int v, cost;
};

struct jmuchie{
	int u, v, cost;
};

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

void citire(vector<muchie> Q[], int &n){
	FILE *f = fopen("apm.in", "r");
	int m; 
	fscanf(f, "%d%d", &n, &m);
	for (int i = 0, u, v; i < m; i++){
		muchie noua;
		fscanf(f, "%d%d%d", &u, &v, &noua.cost);
		noua.v = v - 1;
		Q[u - 1].push_back(noua);
		noua.v = u - 1;
		Q[v - 1].push_back(noua);
	}
	fclose(f);
}

void insert_heap(vector<jmuchie> &VecHeap, vector<muchie> Q[], int x){
	for (int i = 0;  i < (int) Q[x].size(); i++) {
		jmuchie noua;
		noua.u = x;
		noua.v = Q[x][i].v;
		noua.cost = Q[x][i].cost;
		VecHeap.push_back(noua);
		push_heap(VecHeap.begin(), VecHeap.end(), func);
	}
}

int Prim(vector<muchie> Q[], vector<muchie> &T, int n, int vizitat[]){
	vizitat[0]++;
	vector<jmuchie> VecHeap;
	make_heap(VecHeap.begin(), VecHeap.end(), func);
	insert_heap(VecHeap, Q, 0);
	int costmin = 0;
	for (int i = 1; i < n; i++){
		while (vizitat[VecHeap.front().v] && vizitat[VecHeap.front().u]) {
			pop_heap(VecHeap.begin(), VecHeap.end(), func);
			VecHeap.pop_back();
		}
		vizitat[VecHeap.front().v]++;
		muchie noua;
		noua.cost = VecHeap.front().u + 1;
		noua.v = VecHeap.front().v + 1;
		T.push_back(noua);
		costmin += VecHeap.front().cost;

		pop_heap(VecHeap.begin(), VecHeap.end(), func);
		VecHeap.pop_back();

		insert_heap(VecHeap, Q, noua.v - 1);
	}
	return costmin;
}

void afisare(vector<muchie> &T, int costmin){
	FILE *f = fopen("apm.out", "w");
	fprintf(f, "%d\n%d\n", costmin, (int)T.size());
	for (int i = 0; i < (int)T.size(); i++) fprintf(f, "%d %d\n", T[i].v, T[i].cost);
	fclose(f);
}

int main(){
	int n, vizitat[NMAX];
	vector<muchie> Q[NMAX], T;
	citire(Q, n);
	memset(vizitat, 0 , n*4);
	int costmin = Prim(Q, T, n, vizitat);
	afisare(T, costmin);
	return 0;
}