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

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

struct compara{
	bool operator()(const nod &n1, const nod& n2) const
		{return n1.c < n2.c;}
};
multiset <nod, compara> binT;

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} );
	}
	cost.assign(n+1, inf);
	cost[1] = 0;
	binT.insert( (nod){1, 0} );
	
	while (!binT.empty()){
		int x = binT.begin()->n;
		binT.erase(binT.begin());
		if (!viz[x]) {
			viz[x] = 1;
			cost_T += cost[x];
			p.push_back(x);
			
			for (i = 0; i < (int)T[x].size() && (y = T[x][i].y); i++)
				if (!viz[y]){
					c = T[x][i].c;
					if (cost[y] > c){
						binT.insert( (nod) {y, c} );
						cost[y] = c;
					}
				}
		}
	}
	
	printf("%d\n", cost_T);
	for (i = 1; i < (int)p.size(); i++) printf("%d %d\n", p[i - 1], p[i]);
	return 0;
}