#include<stdio.h>
#define infile "apm.in"
#define outfile "apm.out"
#define nmax (200*1000+1)
#define mmax (400*1000+1)
struct muchie
	{
	int x,y,c; //arcul [x,y] cu costul c
	} v[mmax]; //aicim vom salva toate muchiile
int apm[nmax]; //aici vom salva muchiile care formeaza arborele partial de cost minim
char 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 *n, int *m)
	{
	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
	}

int kruskal(struct muchie v[nmax], int apm[nmax], char viz[nmax], int n)
	{
	int i,c=0; //costul minim
	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 (macar unul din noduri sa nu fie vizitat)
			{
			c+=v[i].c; //adaugam costul muchiei
			viz[v[i].x]=viz[v[i].y]=1; //marcam ambele muchii ca vizitate
			apm[++apm[0]]=i; //salvam muchia pe care am adaugato
			}
	return c; //returnam costul minim al arborelui partial
	}

int main()
{
freopen(infile,"r",stdin);
freopen(outfile,"w",stdout);

citire(v,&n,&m); //citire
qsort(v,1,m); //sortam muchiile dupa cost
c=kruskal(v,apm,viz,n); //facem arborele partial de cost minim, si primim costul
printf("%d\n%d\n",c,apm[0]);
int i;
for(i=1;i<n;i++)
	printf("%d %d %d\n",v[apm[i]].x,v[apm[i]].y,apm[i]);

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