#include<fstream>
#include<vector>
using namespace std;
///////////////////////
#define MaxBuffer 8192
char buffer[MaxBuffer];
int bufferIndex=8191;
///////////////////////
vector <pair <int,int> > a[200100],sol;
int n,sum,tata[200100],poz[200100],heap[400100],V[200100],inf=2000000000,nr=1;
inline void read_buffer(istream& in,int& x) {
    int smn=1;
	do {if(++bufferIndex==MaxBuffer) {
			bufferIndex=0;
			in.read(buffer,MaxBuffer);
			}
	}while( (buffer[bufferIndex]<'0'||buffer[bufferIndex]>'9')&&(buffer[bufferIndex]!='-') ); 
	if(buffer[bufferIndex]=='-') {
		smn=-1;
		if(++bufferIndex==MaxBuffer) {
			bufferIndex=0;
			in.read(buffer,MaxBuffer);
			}
		}
	for(x=0;buffer[bufferIndex]>='0'&&buffer[bufferIndex]<= '9';) {
		x=x*10+buffer[bufferIndex]-'0';
		if(++bufferIndex==MaxBuffer) {
			bufferIndex=0;
			in.read(buffer,MaxBuffer);
			}
		}
	x*=smn;
}
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");
	read_buffer(in,n);read_buffer(in,m);
	for(i=0;i<m;i++) {
		read_buffer(in,x);read_buffer(in,y);read_buffer(in,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;
	long long clo=clock();
	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.push_back(pair<int,int>(nod,tata[nod]));
		introdu_apm(nod);
		}
	afis();
	return 0;
}