#include<fstream>
#include<vector>
using namespace std;
vector <pair <int,int> > a[200100];
pair <int,int> sol[200100];
int n,sum,tata[200100],poz[200100],heap[400100],V[200100],inf=2000000000,nr=1,solnr;
void push(int nod) {
	int fiu=nod;nod=0;
	while(fiu!=nod) {
		nod=fiu;
		if(2*nod<nr&&V[heap[fiu]]>V[heap[2*nod]]) fiu=2*nod;
		if(2*nod+1<nr&&V[heap[fiu]]>V[heap[2*nod+1]]) fiu=2*nod+1;
		swap(heap[nod],heap[fiu]);
		swap(poz[heap[nod]],poz[heap[fiu]]);
		}
}
void pop(int nod) {
	while(nod/2&&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_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&&poz[vecin]) {
			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(make_pair(y,c));
		a[y].push_back(make_pair(x,c));
		}
	in.close();
}
void afis() {
	int i;
	ofstream out("apm.out");
	out<<sum<<'\n'<<solnr<<'\n';
	for(i=1;i<=solnr;i++)
		out<<sol[i].first<<" "<<sol[i].second<<'\n';
	out.close();
}
int main() {
	int i,nod;
	
	citire();
	for(i=2;i<=n;V[i++]=inf);
	for(i=2;i<=n;heap[nr]=i,poz[i++]=nr++);
	introdu_apm(1);
	for(i=1;i<n;i++) {
		nod=radacina_heap();
		sum+=V[nod];
		sol[++solnr].first=nod;
        sol[solnr].second=tata[nod];
		introdu_apm(nod);
		}
	afis();
	return 0;
}