#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[200001];
vector <nod> cost;
vector <int> p;
int n, m, poz, viz[200001];

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