#include<fstream>
#include<vector>
using namespace std;
vector <pair <int,int> > a[200100],sol;
int n,sum,tata[200100],poz[200100],heap[200100],V[200100],inf=1<<30,nr=1;
void push(int nod) {
	int fiu;
	do {fiu=0;
		if(2*nod<nr) {
			if(V[heap[nod]]>V[heap[2*nod]])
				fiu=2*nod;
			if(2*nod+1<nr&&V[heap[2*nod+1]]<V[heap[2*nod]])
				fiu=2*nod+1;
			}
		if(fiu) {
			swap(heap[nod],heap[fiu]);
			swap(poz[heap[nod]],poz[heap[fiu]]);
			nod=fiu;
			}
	}while(fiu);
}
void pop(int nod) {
	while(nod>1&&V[heap[nod]]<V[heap[nod/2]]) {
		swap(heap[nod],heap[nod/2]);
		swap(poz[heap[nod]],poz[heap[nod/2]]);
		nod/=2;
	}
}
int radacina_heap() {
	int nod=heap[1];
	heap[1]=heap[--nr];
	poz[heap[1]]=poz[heap[nr]];
	push(1);
	poz[nod]=0;
	return nod;
}
void introdu_heap(int nod) {
	heap[nr]=nod;
	poz[nod]=nr++;
	pop(poz[nod]);
}
void introdu_apm(int nod) {
	int i,m=a[nod].size(),vecin;
	for(i=0;i<m;i++) {
		vecin=a[nod][i].first;
		if(V[vecin]>a[nod][i].second) {
			V[vecin]=a[nod][i].second;
			tata[vecin]=nod;
			pop(poz[vecin]);
			}
		}
}
void citire() {
	int i,x,y,c,m;
	ifstream in("apm.in");
	in>>n>>m;
	for(i=0;i<m;i++) {
		in>>x>>y>>c;
		a[x].push_back(pair<int,int>(y,c));
		a[y].push_back(pair<int,int>(x,c));
		}
	in.close();
}
void afis() {
	int i,m=sol.size();
	ofstream out("apm.out");
	out<<sum<<'\n'<<m<<'\n';
	for(i=0;i<m;i++)
		out<<sol[i].first<<" "<<sol[i].second<<'\n';
	out.close();
}
int main() {
	int i,nod;
	citire();
	//initializare
	for(i=2;i<=n;V[i++]=inf);
	introdu_apm(1);
	for(i=2;i<=n;)
		introdu_heap(i++);
	//get APM
	for(i=1;i<n;i++) {
		nod=radacina_heap();
		sum+=V[nod];
		sol.push_back(pair<int,int>(nod,tata[nod]));
		introdu_apm(nod);
		}
	afis();
	return 0;
}