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

using namespace std;

class TreeNode{
public:
	int val;
	TreeNode *parent;
	TreeNode *child_to_update;
	TreeNode(int v) : val(v), parent(NULL), child_to_update(NULL) {}

};

class Trio{
public:
	int x, y, c;
	Trio(int x, int y, int c) : x(x), y(y), c(c) {}
};

int n, m, x, y, c, cnt, cost;
vector<Trio> adj;

vector<struct TreeNode*> trees;
vector<int> ranks;
vector<pair<int, int>> ans;

void make_set(int a){
	trees.push_back(new TreeNode(a));
}

int find(int a){
	TreeNode *t = trees.at(a), *aux, *rad;
	int ret;
	while(t->parent != NULL){
		aux = t;
		t = t->parent;
		t->child_to_update = aux; 
	}
	rad = t;
	while((aux = t->child_to_update)){
		t->child_to_update = NULL;
		aux->parent = rad;
		t = aux;
	}
	return rad->val;
}

void link(int a, int b){
	int pa = find(a);
	int pb = find(b);
	TreeNode *ppa = trees.at(pa);
	TreeNode *ppb = trees.at(pb);
	ppb->parent = ppa;
}

void uunion(int a, int b){
	if(ranks.at(a) > ranks.at(b)){
		link(a, b);
	}else{
		link(b, a);
		if(ranks.at(a) == ranks.at(b)){
			ranks.at(b)++;
		}
	}
}

bool comp(Trio t1, Trio t2){
	return (t1.c < t2.c);
}

int main(){
	freopen("apm.in", "r", stdin);
	freopen("apm.out", "w", stdout);
	scanf("%d%d", &n, &m);
	for(int i = 0; i < n; i++){
		make_set(i);
		ranks.push_back(0);
	}
	for(int i = 0; i < m; i++){
		scanf("%d%d%d", &x, &y, &c);
		adj.push_back(Trio(--x,--y, c));
	}

	sort(adj.begin(), adj.end(), comp);

	for(int i = 0; i < adj.size(); i++){
		Trio t = adj[i];
		if(find(t.x) != find(t.y)){
			uunion(t.x, t.y);
			cnt++;
			cost += t.c;
			ans.push_back(make_pair(t.x, t.y));
		}
		if(cnt == n-1) break;
	}
	printf("%d\n%d\n", cost, cnt);
	for(int i = 0; i < ans.size(); i++){
		printf("%d %d\n", ans[i].first+1, ans[i].second+1);
	}
	return 0;
}