#include<stdio.h>
using namespace std;
int n,m,nh,ct;

struct nod
{
	int v,c;
	nod *adr;
};

struct muchie
{
	int v1,v2;
	muchie *adr;
};

struct heap
{
	int v1,v2,c;
};

nod *g[200002];
muchie *st;
heap h[400002];
char viz[200002];

void citire()
{
	int i,x,y,c;
	nod *p;
	scanf("%d %d",&n,&m);
	for(i=1;i<=m;++i)
	{
		scanf("%d %d %d",&x,&y,&c);
		
		p=new nod;
		p->v=y;
		p->c=c;
		p->adr=g[x];
		g[x]=p;
		
		p=new nod;
		p->v=x;
		p->c=c;
		p->adr=g[y];
		g[y]=p;
	}
}

void swap(int a,int b)
{
	heap aux;
	aux=h[a];
	h[a]=h[b];
	h[b]=aux;
}

void heapjos(int k)
{
	int x,fs,fd;
	do
	{
		x=0;
		fs=k*2;
		fd=k*2+1;
		if(fs<=nh)
		{
			x=fs;
			if(fd<=nh && h[fd].c < h[x].c)
				x=fd;
			if(h[x].c >= h[k].c)
				x=0;
		}
		if(x)
		{
			swap(x,k);
			k=x;
		}
	}while(x);
}

void heapsus(int k)
{
	int t;
	t=k/2;
	while(k>1 && h[k].c < h[t].c)
	{
		swap(k,t);
		k=t;
		t=k/2;
	}
}

void add(int x,int y)
{
	muchie *q;
	q=new muchie;
	q->v1=x;
	q->v2=y;
	q->adr=st;
	st=q;
}
	
void sterg()
{
	h[1]=h[nh];
	--nh;
	heapjos(1);
}

void prim()
{
	int v1,v2;
	nod *p;
	for(p=g[1];p;p=p->adr)
	{
		++nh;
		h[nh].v1=1;
		h[nh].v2=p->v;
		h[nh].c=p->c;
		heapsus(nh);
	}
	viz[1]=1;
	while(nh)
	{
		v1=h[1].v1;
		v2=h[1].v2;
		if(viz[v1]==1 && viz[v2]==0)
		{
			ct+=h[1].c;
			add(v1,v2);
			viz[v2]=1;
			sterg();
			for(p=g[v2];p;p=p->adr)
				if(viz[p->v]==0)
				{
					++nh;
					h[nh].v1=v2;
					h[nh].v2=p->v;
					h[nh].c=p->c;
					heapsus(nh);
				}
			
		}
		else
			sterg();
	}
}

void scrie()
{
	muchie *p;
	printf("%d\n%d\n",ct,n-1);
	for(p=st;p;p=p->adr)
		printf("%d %d\n",p->v1,p->v2);
}


int main()
{
	freopen("apm.in","r",stdin);
	freopen("apm.out","w",stdout);
	citire();
	prim();
	scrie();
	fclose(stdin);
	fclose(stdout);
	return 0;
}