/**
 * Proiectarea Algoritmilor, 2016
 * Lab 9: Arbori minimi de acoperire
 *
 * @author  adinu
 * @email   [email protected]
 */

#include <iostream>
#include <fstream>
#include <vector>
#include <utility>
#include <queue>
#include <algorithm>

struct Edge {
	int x, y, cost;
	
	Edge(int x, int y, int cost) {
		this->x = x;
		this->y = y;
		this->cost = cost;
	}
};

bool edgeCompare(const Edge& firstElem, const Edge& secondElem) {
  return firstElem.cost < secondElem.cost;

}

int get_root(int node, int p[]) {
	
	while (node != p[node]) {
		node = p[node];
	}
	return node;
} 

void kruskal(std::vector<Edge>& E, int V, int &cost, std::vector<std::pair<int, int> >& AMA) {
	
	// sortare muchii crescator dupa costuri
    std::sort(E.begin(), E.end(), edgeCompare);
    
    int parent[V];
    for (int i = 0; i <= V; i++) {
    	parent[i] = i;
    }
    
    for (unsigned int i = 0; i < E.size(); i++) {
    	int x, y;
    	x = E[i].x;
    	y = E[i].y;
    	
    	if (get_root(x, parent) != get_root(y, parent)) {
    		AMA.push_back(std::make_pair(x, y));
    		cost += E[i].cost;
    		parent[get_root(y, parent)] = get_root(x, parent);
    	}
    }
}

int main() {

  	int num_nodes, num_edges, x, y, c, cost;

  	FILE *fin = fopen("apm.in", "r");
  	FILE *fout = fopen("apm.out", "w");
  
  	fscanf(fin, "%d %d", &num_nodes, &num_edges);
  	std::vector<Edge> E;
  	std::vector<std::pair<int, int> > AMA;

  	cost = 0;

  	for (int i = 1; i <= num_edges; i++) {
    	fscanf(fin, "%d %d %d", &x, &y, &c);
    	struct Edge e(x, y, c);
    	E.push_back(e);
  	}

  	kruskal(E, num_nodes, cost, AMA);
  	fprintf(fout, "%d\n", cost);
  	fprintf(fout, "%ld\n", AMA.size());
  	
  	for (unsigned int i = 0; i < AMA.size(); i++) {
		fprintf(fout, "%d %d\n", AMA[i].first, AMA[i].second);
	}
	
	fclose(fout);
}