#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];
int n,m,cost;

int main() {
	freopen("apm.in","r",stdin);
	freopen("apm.out","w",stdout);
	scanf("%d %d",&n,&m);
	for (int i=1;i<=m;i++) {
		int a,b,c;
		scanf("%d %d %d",&a,&b,&c);
		v[a].push_back(mkmuc(a,b,c));
		v[b].push_back(mkmuc(b,a,c));
	}
	int start = n/4;
	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));
	}
	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;
}