#include <stdio.h>

const int maxn=200005,INF=200000005;
struct nod {
	int inf,c;
	nod *next;
} *A[maxn];
struct arc {
	int a,b;
	arc *next;
} *Sol;
int N,M,i,H[maxn],poz[maxn],D[maxn],vm[maxn],hp,Sapm;

void add_v(int x, int y, int z) // adauga pe y in lista de vecini a lui x
{
	nod *q=new nod;
	q->inf=y;
	q->c=z;
	q->next=A[x];
	A[x]=q;
}

void swap(int &a, int &b) //interschimbare
{
	int aux;
	aux=a;
	a=b;
	b=aux;
}
int min(int a, int b)
{
	if(a<b) return a;
	return b;
}

void upheap(int k)
{
	while(k>1 && D[H[k]]<D[H[k/2]])
	{
		swap(poz[H[k]],poz[H[k/2]]);
		swap(H[k],H[k/2]);		
		k/=2;
	}
}
void downheap(int k)
{
	int son;
	do
	{
		son=0;
		if(2*k<=hp)
		{
			son=2*k;
			if(2*k+1<=hp && D[H[son]]>D[H[2*k+1]])
				son=2*k+1;
		}
		if(D[H[son]]>D[H[k]]) son=0;
	if(son)
	{
		swap(poz[H[k]],poz[H[son]]);
		swap(H[k],H[son]);
		k=son;
	}
	}
	while(son);
}
void insert(int k) //introducere in heap
{
	hp++;
	H[hp]=k;
	poz[k]=hp;
	upheap(hp);
}
int radacina() // extrage radacina
{
	int x=H[1];
	swap(poz[H[1]],poz[H[hp]]);
	swap(H[1],H[hp]);
	hp--;
	downheap(1);
	poz[x]=0;
	return x;
}

void update_vecini(int k) //verifica vecinii , vm= vecinul cel mai apropiat
{
	for(nod *x=A[k];x;x=x->next)
	{
		D[x->inf]=min(D[x->inf],x->c);
		if(D[x->inf] == x->c) vm[x->inf]=k;
	}
}
void update_heap(int k) // reface heap-ul dupa posibile modificari
{
	for(nod *x=A[k];x;x=x->next)
	 if(poz[x->inf]) upheap(poz[x->inf]);
}

void adauga_muchie(int x, int y) //adauga muchia in lista solutiei
{
	arc *q=new arc;
	q->a=x;
	q->b=y;
	q->next=Sol;
	Sol=q;
}

void creare_arbore()
{
	for(i=2;i<=N;i++) D[i]=INF;
	D[1]=0;
	update_vecini(1);
	for(i=2;i<=N;i++) insert(i);
	for(i=1;i<N;i++)
	{
		int x=radacina();
		update_vecini(x);
		Sapm+= D[x];
		adauga_muchie(x,vm[x]);
		update_heap(x);
	}
}

void afisare_muchii()
{
	for(;Sol;Sol=Sol->next)
		printf("%d %d\n",Sol->a,Sol->b);
}

int main()
{
	freopen("apm.in","r",stdin);
	freopen("apm.out","w",stdout);
	scanf("%d %d",&N,&M);
	for(i=1;i<=M;i++) 
	{
		int x,y,z;
		scanf("%d %d %d",&x,&y,&z);
		add_v(x,y,z);
		add_v(y,x,z);
	}
	creare_arbore();
	printf("%d\n%d\n",Sapm,N-1);
	afisare_muchii();
}