#include <iostream>
#include <stdio.h>
#include <queue>
#include <stdlib.h>
#include <algorithm>
#include <vector>

struct Compare 
{
	bool operator() (std::pair< std::pair<int, int>, int > const& a, std::pair< std::pair<int, int>, int > const &b) const {
		return a.second > b.second;
	}
};

typedef struct Arb
{
	int size;
	int node;
	Arb *next;
	Arb *head;
}Arbs;

Arbs * FindSet(Arbs* a) {
	return a->head;
}

Arbs * MakeSet(int i) {
	Arbs *arb = (Arbs*)malloc(sizeof(Arbs));
	arb->size = 1;
	arb->node = i;
	arb->next = NULL;
	arb->head = arb;
	return arb;
}

void Union(Arbs* a, Arbs* b) {
	Arbs* auxA = a->head;
	Arbs* auxB = b->head;
	while (auxA->next != NULL) {
		auxA->size += b->size;
		auxA = auxA->next;
	}

	auxA->next = auxB;
	auxA->size += b->size;
	auxB->head = a->head;

	while (auxB->next != NULL) {
		auxB->size = auxA->size;
		auxB = auxB->next;
		auxB->head = a->head;
	}
	auxB->size = auxA->size;
}

int main() {
	FILE *in = fopen("apm.in", "r");
	FILE *out = fopen("apm.out", "w");

	int N, M;
	fscanf(in, "%d %d", &N, &M);

	std::vector<std::pair<int, int> > resultVect;
	
	std::priority_queue<std::pair<std::pair<int, int>, int>, std::vector<std::pair<std::pair<int, int>, int> >, Compare> priorQueue;

	for (int i = 0; i < M; i++) {
		int x, y, c;
		fscanf(in, "%d %d %d", &x, &y, &c);
		priorQueue.push(std::make_pair(std::make_pair(x - 1, y - 1), c));
	}
	
	std::vector<Arbs*> arbsVect;
	for (int i = 0; i < N; i++) {
		arbsVect.push_back(MakeSet(i));
	}

	int bestPlanCost = 0;
	for (int i = 0; i < M; i++) {
		int node1, node2, edgeCost;
		
		node1 = priorQueue.top().first.first;
		node2 = priorQueue.top().first.second;
		edgeCost = priorQueue.top().second;
		priorQueue.pop();
		
		if (FindSet(arbsVect.at(node1)) != FindSet(arbsVect.at(node2))) {
			if (arbsVect.at(node1)->size > arbsVect.at(node2)->size) 
				Union(arbsVect.at(node1), arbsVect.at(node2));
			else 
				Union(arbsVect.at(node2), arbsVect.at(node1));
			bestPlanCost += edgeCost;
			resultVect.push_back(std::make_pair(node2, node1));
		}
	}

	int size = resultVect.size();
	fprintf(out, "%d\n", bestPlanCost);
	fprintf(out, "%d\n", size);

	for (uint i = 0; i < resultVect.size(); i++) {
		fprintf(out, "%d %d\n", resultVect[i].first + 1, resultVect[i].second + 1);
	}

	return 0;	
}