#include<stdio.h>
#include<vector>
#define inf 2000000000
#define x first
#define c second
#define nmax 200005
using namespace std;
int d[nmax],x[nmax],t[nmax],poz[nmax],n,nn,m,cost;
vector < pair <int,int> > l[nmax];
void cit(){
	FILE *f;
	int i,a,b,c;
	f=fopen("apm.in","r");
	fscanf(f,"%d%d",&n,&m);
	for(i=1;i<=m;i++){
		fscanf(f,"%d%d%d",&a,&b,&c);
		l[a].push_back(make_pair(b,c));
		l[b].push_back(make_pair(a,c));
	}
	fclose(f);
}
void swap(int i,int j){
	int aux;
	aux=x[i];
	x[i]=x[j];
	x[j]=aux;
	poz[x[i]]=i;
	poz[x[j]]=j;
}
void heapUp(int k){
	if(k>1)
		if(d[x[k/2]]>d[x[k]]){
			swap(k,k/2);
			heapUp(k/2);
		}
}
void heapDown(int k){
	int st,dr,i;
	if(2*k<=n){
		st=d[x[2*k]];
		if(2*k+1<=n)
			dr=d[x[2*k+1]];
		else
			dr=st+1;
		if(st<dr)
			i=2*k;
		else
			i=2*k+1;
		if(d[x[k]]>d[x[i]]){
			swap(k,i);
			heapDown(i);
		}
	}
}
void buildHeap(){
	int i;
	for(i=1;i<=n;i++)
		heapUp(i);
}
int scoateHeap(){
	swap(1,n);
	n--;
	heapDown(1);
	poz[x[n+1]]=0;
	return x[n+1];
}
void prim(){
	int k,i;
	nn=n;
	for(i=1;i<=n;i++){
		x[i]=i;
		d[i]=inf;
		poz[i]=i;
	}
	d[1]=0;
	buildHeap();
	while(n>0){
		k=scoateHeap();
		cost+=d[k];
		for(unsigned int i=0;i<l[k].size();i++)
			if(poz[l[k][i].x]!=0&&l[k][i].c<d[l[k][i].x]){
				d[l[k][i].x]=l[k][i].c;
				t[l[k][i].x]=k;
				heapUp(poz[l[k][i].x]);
			}
	}
}
void afis(){
	FILE *f;
	f=fopen("apm.out","w");
	fprintf(f,"%d\n%d\n",cost,nn-1);
	for(int i=2;i<=nn;i++)
		fprintf(f,"%d %d\n",i,t[i]);
	fclose(f);
}
int main(){
	cit();
	prim();
	afis();
	return 0;
}