#include<iostream>
#include<fstream>
using namespace std;
typedef struct muchie{
	int x,y,c;
}MUCHII;
MUCHII v[400001],APM[200001];
int n,m,nAPM,costAPM;
int T[200001],rang[200001];
ifstream f("apm.in");
ofstream g("apm.out");
void citire(){
	f>>n>>m;
	for(int i=1;i<=m;i++)
		f>>v[i].x>>v[i].y>>v[i].c;
}
void quicksort(MUCHII v[],int left,int right){
	int i=left,j=right,pivot=v[left+(right-left)/2].c;
	while(i<=j){
		while(v[i].c<pivot)
			i++;
		while(v[j].c>pivot)
			j--;
		if(i<=j){
			swap(v[i],v[j]);
			i++;
			j--;
		}
	}
	if(left<j)
		quicksort(v,left,j);
	if(i<right)
		quicksort(v,i,right);
}
void makeset(int x){
	T[x]=x;
	rang[x]=1;
}
void reuniune(int x,int y){  
	if(rang[x]>rang[y])
		T[y]=x;              
	else
		if(rang[y]>rang[x])
			T[x]=y;
	else
		if(rang[x]==rang[y]){
			T[x]=y;           
			rang[y]++;
		}
}
int radacina(int x){
	int i,aux;       
	for(i=x;i!=T[i];i=T[i]);     
	while(x!=T[x]){           
		aux=T[x];
		T[x]=i;
		x=aux;
	}
	return i;
}
void kruskal(){
	for(int i=1;i<=n;i++)
		makeset(i);
	quicksort(v,1,m);
	for(int i=1;i<=m;i++)
		if(radacina(v[i].x)!=radacina(v[i].y)){
			nAPM++;
			APM[nAPM].x=v[i].x;
			APM[nAPM].y=v[i].y;
			APM[nAPM].c=v[i].c;
			costAPM=costAPM+v[i].c;
			reuniune(radacina(v[i].x),radacina(v[i].y));
		}
}
void afisare(){
	g<<costAPM<<"\n"<<n-1<<"\n";
	for(int i=1;i<=n-1;i++)
		g<<APM[i].x<<" "<<APM[i].y<<"\n";	
}
	
int main(){
	citire();
	nAPM=0;
	costAPM=0;
	kruskal();
	afisare();
	
	return 0;
}