#include <bits/stdc++.h>

using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");
struct cell{
	int index,value;
	
	
};
typedef struct nod{
	int val,cost;
	nod* next;
	
}*graf;
const int inf=1e9;
graf lda[100001];
cell heap[100001];
int N;
map <int,int> link;//index la nod->pozitia in heap
map <int,pair<int,int> > edges;//index la nod->nodul de la care vine legatura + costul
void add(graf &a,int val,int cost){
	graf b=new nod;
	b->val=val;
	b->cost=cost;
	b->next=a;
	a=b;
	
	
}

void sift(int k){
	int son;
	do {
		son=0;
		if (2*k<=N) {
		son=2*k;
		if (2*k+1<=N&&heap[2*k+1].value<heap[2*k].value)son =2*k+1;
		if (heap[son].value>=heap[k].value) son=0;
		
	}
		if (son) swap(link[heap[k].index],link[heap[son].index]),swap(heap[k],heap[son]),k=son;
	}while(son);
	
	
}

void perlocate(int k){
	cell key=heap[k];
	while(k>1&&key.value<heap[k/2].value){
		swap(heap[k],heap[k/2]);
		swap(link[heap[k].index],link[heap[k/2].index]);
		k/=2;
	}
		//heap[k]=key;
}


void cut(int k){
	link[heap[k].index]=-1;
	link[heap[N].index]=1;
	heap[k]=heap[N];

	--N;
	//if (k>1&&heap[k]>heap[k/2]) perlocate(k);
    sift(k);
	
}
void insert(cell key){
	heap[++N]=key;
	link[heap[N].index]=N;
	perlocate(N);
	
}
void update(int k,int newv){
	heap[k].value=newv;
	perlocate(k);
	
}


int main(){
	int n,m;
	fin >>n>>m;
	for(int i=1;i<=m;i++){
		int a,b,c;
		fin>>a>>b>>c;
		add(lda[a],b,c);
		add(lda[b],a,c);
	}
	cell x;
	x.index=1;
	x.value=0;
	insert(x);
	x.value=inf;
	for(int i=2;i<=n;i++){
		x.index=i;
		insert(x);
	}
	//for(int i=1;i<=n;i++) cout <<heap[i].index<<" "<<heap[i].value<<endl;
	int vp=0,sum=0;
	//vector < pair<int,int> >v;
	int v1[200010],v2[200010];
	while(N){
		 cell source=heap[1];
		 cut(1);
		 for(graf it=lda[source.index];it!=NULL;it=it->next)
			 if (it->cost<heap[link[it->val]].value) {
				 update(link[it->val],it->cost);
				 edges[it->val].first=source.index;
				 edges[it->val].second=it->cost;
			}
		//cout <<source.index<<" "<<edges[source.index].first<<" "<<edges[source.index].second<<endl;
		if (vp!=0){
			sum+=edges[source.index].second;
			v1[vp]=source.index;
			v2[vp]=edges[source.index].first;
			//v.push_back(make_pair(source.index,edges[source.index].first));
		}
		vp++;
	}
	vp--;
	fout <<sum<<endl<<vp<<endl;
	for(unsigned int i=1;i<=vp;i++) fout <<v1[i]<<" "<<v2[i]<<endl;
	return 0;
}