#include<cstdio>
#include<vector>
#include<set>
#define MAX_N 200001
#define inf 0xfffffff
using namespace std;

struct muchie {int y, c;};
struct nod {int n, c;};
vector <muchie> T[MAX_N], edges;
int n, m, poz, viz[MAX_N], cost[MAX_N];

class heap{
	vector <int> elem, node_on_pos, src_node;
	
	void Swap(int i, int j){
		swap(elem[i], elem[j]);
		swap(node_on_pos[i], node_on_pos[j]);
		swap(src_node[i], src_node[j]);
	}
	
	void Down_Heap(int i){
		int fiu;
		
		while (i <= (int)(elem.size() - 1) / 2){
			fiu = 2 * i;
			if (fiu + 1 <= (int)elem.size() - 1 && elem[fiu+1] < elem[fiu]) fiu++;
			if (elem[i] > elem[fiu]){
				Swap(i, fiu);
				i = fiu;
			}
			else break;
		}
	}
	
	void Up_Heap(int i){
		int tata = i/2;
		
		while (i > 1 && elem[i] < elem[tata]){
			Swap(i, tata);
			i = tata; tata = i/2;
		}
	}
public:	
	heap(){
		elem.assign(1, 0);
		node_on_pos.assign(MAX_N, 0);
		src_node.assign(MAX_N, 0);
	}
	
	void insert(const int& node1, const int& node2, const int &c){ // inserez muchia node1-node2 de cost c
		src_node[elem.size()] = node1;
		node_on_pos[elem.size()] = node2;
		elem.push_back(c);
		Up_Heap(elem.size() - 1);
	}
	
	void pop(){	//sterge nodul din top
		Swap(1, elem.size() - 1);
		node_on_pos[elem.size() - 1] = src_node[elem.size() - 1] = 0;
		elem.pop_back();
		Down_Heap(1);
		Up_Heap(1);
	}
	
	int top_src() { return src_node[1];}
	int top_adj_node() { return node_on_pos[1];}
	int top_cost() { return elem[1]; }
	bool empty() { return !(elem.size() > 1); }
} H;

int main(){
	freopen("apm.in", "r", stdin),	freopen("apm.out", "w", stdout);
	scanf("%d %d", &n, &m);
	int i, x, y, c, cost_T = 0;
	
	for (i = 0; i < m; i++){
		scanf("%d %d %d", &x, &y, &c);
		T[x].push_back( (muchie){y, c} );
		T[y].push_back( (muchie){x, c} );
	}
	
	for (i = 0; i <= n; i++) cost[i] = inf;
	cost[1] = 0;
	H.insert(1, 1, 0);
	
	while (!H.empty() && (int)edges.size() < n){		//las costurile proaste in heap, oricum le sar cand dau de ele
		x = H.top_src(); y = H.top_adj_node(); c = H.top_cost();
		H.pop();
		
		if (!viz[y]){
			viz[y] = 1;
			cost_T += c;
			edges.push_back( (muchie) {x, y} );
		
			for (i = 0, x = y; i < (int)T[x].size() && (y = T[x][i].y); i++)
				if (!viz[y]){
					c = T[x][i].c;
					if (cost[y] > c){
						H.insert(x, y, c);
						cost[y] = c;
					}
				}
		}
	}
	
	printf("%d\n%d\n", cost_T, n - 1);
	for (i = 1; i < (int)edges.size(); i++) printf("%d %d\n", edges[i].y, edges[i].c);
	return 0;
}