#include <cstdio>
#include <vector>
#include <queue>
using namespace std;

struct muchie {
	int s,d,c;
};

struct comp {
	bool operator() (muchie &a,muchie &b) {
		return a.c > b.c;
	}
};

inline muchie mkmuc(int s,int d,int c) {
	muchie nou;
	nou.s = s;
	nou.d = d;
	nou.c = c;
	return nou;
}

priority_queue <muchie,vector<muchie>,comp> q;
vector <muchie> r;
vector <muchie> v[200005];
vector <muchie> :: iterator it;
bool viz[200005];
char buf[500005],bp;
int n,m,cost;

inline void apm(int start) {
	viz[start] = true;
	for (it=v[start].begin();it!=v[start].end();it++) 
		q.push(mkmuc(start,(*it).d,(*it).c));
	while (!q.empty()) {
		muchie nod = q.top(); q.pop();
		if (viz[nod.d]) continue;
		viz[nod.d] = true;
		cost += nod.c;
		r.push_back(mkmuc(nod.s,nod.d,0));
		for (it=v[nod.d].begin();it!=v[nod.d].end();it++)
			q.push(mkmuc(nod.d,(*it).d,(*it).c));
	}
}

int cit() {
	if (buf[bp] == 0 || bp >= 500000) {
		fread(buf,1,500000,stdin);
		bp = 0;
	}
	int res = 0;
	int semn = 1;
	while (buf[bp] == ' ' || buf[bp] == '\n') bp++;
	if (buf[bp] == '-') semn = -1,bp++;
	while ('0' <= buf[bp] && buf[bp] <= '9') 
		res = 10*res + buf[bp]-'0',bp++;
	if (bp  >= 500000) {
		fread(buf,1,500000,stdin);
		bp = 0;
	}
	while ('0' <= buf[bp] && buf[bp] <= '9') 
		res = 10*res + buf[bp]-'0',bp++;
	return res*semn;
}

int main() {
	freopen("apm.in","r",stdin);
	freopen("apm.out","w",stdout);
	n = cit(); m = cit();
	for (int i=1;i<=m;i++) {
		int a=cit(),b=cit(),c=cit();
		v[a].push_back(mkmuc(a,b,c));
		v[b].push_back(mkmuc(b,a,c));
	}
	apm(1);
	printf("%d\n%d\n",cost,n-1);
	for (it=r.begin();it!=r.end();it++) {
		printf("%d %d\n",(*it).s,(*it).d);
	}
	return 0;
}