#include<stdio.h>
#include<algorithm>
#define infile "apm.in"
#define outfile "apm.out"
#define nmax (200*1000+1)
#define mmax (400*1000+1)
using namespace std;
struct muchie
	{
	int x,y,c; //arcul [x,y] cu costul c
	} v[mmax]; //aicim vom salva toate muchiile
struct lista
	{
	int n,p; //nodul....respectiv pozitia fratelui anterior
	} l[2*nmax]; //avem nevoie de dublu, deoarece avem muchii.....(nu arce:P)
int p[nmax]; //salveaza pozitia ultimului copil din lista
int nr; //numarul de elemente din lista
int apm[nmax]; //aici vom salva muchiile care formeaza arborele partial de cost minim
int viz[nmax]; //stim daca un nod a fost luat sau nu:P
int n,m; //numarul de noduri respectiv muchii
int c; //costul minim obtinut de arborele partial

void citire(struct muchie v[mmax])
	{
	int i;
	scanf("%d %d",&n,&m);
	for(i=1;i<=m;i++)
		scanf("%d %d %d\n",&v[i].x,&v[i].y,&v[i].c); //citim muchia [x,y] cu costul c
	}

/*
int divide(struct muchie v[mmax], int p, int q)
	{
	struct muchie a=v[p]; //elementul ce trebuie plasat corect
	while(p<q)
		{
		while(p<q && v[q].c>=a.c) q--; //cat timp elementele din dreapta sunt mai mari
		v[p]=v[q]; //am gasit element mai mic in partea dreapta...il mutam
		while(p<q && v[p].c<=a.c) p++; //cat timp elementele din partea stanga sunt mai mici
		v[q]=v[p]; //am gasit un element in partea stanga mai mare...il mutam in partea dreapta
		}
	v[p]=a; //punem elementul la pozitia p
	return p; //returnam pozitia
	}

void qsort(struct muchie v[mmax], int p, int q)
	{
	int m=divide(v,p,q);
	if(m-1>p) qsort(v,p,m-1); //sortam partea stanga
	if(m+1<q) qsort(v,m+1,q); //sortam partea dreapta
	}
*/
void add(struct lista l[2*nmax], int p[nmax], int m, int x, int y)
	{
	l[m].p=p[x]; l[m].n=y; p[x]=m; //adaugam nodul in lista...si actualizam in vectorul de pozitii
	}

void dfs(struct lista l[2*nmax], int p[nmax], int viz[nmax], int n, int mi) 
	{
	int ul=p[n]; //pozitia ultimului copil
	viz[n]=mi; //marcam ca am vizitat
	while(ul)
		{
		if(viz[l[ul].n]!=mi)
			dfs(l,p,viz,l[ul].n,mi); //parcurgem copii nodului
		ul=l[ul].p; //pozitia altui frate :P
		}
	}

int kruskal(struct lista l[2*nmax], int p[nmax], int nr, struct muchie v[nmax], int apm[nmax], int viz[nmax], int n, int m)
	{
	int i,c=0; //costul minim
	for(i=1;i<=n;i++) viz[i]=i; //pt inceput....fiecare nod nu este vizitat (adica apartine singur propriei sale componente conexe)
	for(i=1;apm[0]<n-1;i++) //luam muchii si punem....cat timp nu sau selectat n-1 muchii
		if(viz[v[i].x]!=viz[v[i].y]) //daca muchia nu formeaza un arc (adica cele doua noduri fac parte din componente conexe diferite)
			{
			c+=v[i].c; //adaugam costul muchiei
			//afla unim cele doua componente conexe....salvand la cel cu valoare mai mare...pe cel cu valoare mai mica
			if(viz[v[i].x]<viz[v[i].y]) dfs(l,p,viz,v[i].y,viz[v[i].x]);
			else dfs(l,p,viz,v[i].x,viz[v[i].y]);
			apm[++apm[0]]=i; //salvam muchia pe care am adaugato
			//adaugam in lista muchia (doua arce:P)
			add(l,p,++nr,v[i].x,v[i].y);
			add(l,p,++nr,v[i].y,v[i].x);
			}
	return c; //returnam costul minim al arborelui partial
	}

int cmp(muchie a, muchie b)
{
	return a.c<b.c;
}
		
		
int main()
{
int i;
freopen(infile,"r",stdin);
freopen(outfile,"w",stdout);

citire(v); //citire
//qsort(v,1,m); //sortam muchiile dupa cost
sort(v+1,v+m+1,cmp);
c=kruskal(l,p,nr,v,apm,viz,n,m); //facem arborele partial de cost minim, si primim costul

printf("%d\n%d\n",c,apm[0]); //afisem costul minim si numarul de muchii
//afisem muchiile
for(i=1;i<=apm[i];i++)
	printf("%d %d\n",v[apm[i]].x,v[apm[i]].y);

fclose(stdin);
fclose(stdout);
return 0;
}