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

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

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, int& edg_number) {
	
	// 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)) {
    		edg_number++;
    		E[i].in_apm = true;
    		cost += E[i].cost;
    		parent[get_root(y, parent)] = get_root(x, parent);
    	}
    }
}

int main() {

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

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

  	cost = 0;
	nr = 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, nr);
  	
  	fprintf(fout, "%d\n", cost);
  	fprintf(fout, "%d\n", nr);
  	
  	for (unsigned int i = 0; i < num_edges; i++) {
  		if (E[i].in_apm) {
			fprintf(fout, "%d %d\n", E[i].x, E[i].y);
		}
	}
	
	fclose(fout);
}