#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <list>

#define INF 0x3f3f3f3f

typedef struct
{
	int x,y,c;
	bool bif;
} muchie;

typedef struct _nod
{
	std::list<muchie*> m_adiac;
	std::list<struct _nod *> adiac;
	bool bif;
	int dist;
	int hp_pos;
} nod;

muchie a[400000];
nod b[200000];
nod * hp[200000];
int hplen;

inline bool hplesser(int a,int b)
{
	return (hp[a]->dist)<(hp[b ]->dist);
}

inline void hp_swap(int a, int b)
{
	nod * aux = hp[a];
	hp[a]=hp[b];
	hp[b]=aux;
	hp[a]->hp_pos=a;
	hp[b]->hp_pos=b;
}

void hpdown(int i)
{
	while (1) {
		int p1=(i<<1)+1;
		int p2=(i<<1)+2;
		int max=i;
		if ((p1<hplen)&hplesser(p1,max))
			max=p1;
		if ((p2<hplen)&hplesser(p2,max))
			max=p2;
		if (max!=i)
			hp_swap(i, max);
		else 
			break;
		i=max;
	}
}

void hpup(int i)
{
	while (i)
	{
		int np=((i+1)>>1)-1;
		if (hplesser(i,np))
			hp_swap(i,np);
		else 
			break;
		i=np;
	}
}

void createhp(int len)
{
	hplen=len;
	for (int i=(len/2)-1; i>=0; i--)
		hpdown(i);
}

nod * hpextractmax()
{
	nod * max = hp[0];
	hp[0]=hp[--hplen];
	hpdown(0);
	return max;
}

FILE *fin=fopen("apm.in","r");
FILE *fout=fopen("apm.out","w");

bool cmp(const muchie & a, const muchie & b)
{
	return a.c<b.c;
}

int main (int argc, char * const argv[]) {
	int n,m;
    fscanf(fin, "%d %d", &n, &m);
	for (int i=0; i<m; i++)
	{
		fscanf(fin, "%d %d %d",&a[i].x,&a[i].y,&a[i].c);
		a[i].x--;
		a[i].y--;
		a[i].bif=false;
		b[a[i].x].m_adiac.push_back(&a[i]);
		b[a[i].x].adiac.push_back(&b[a[i].y]);
		b[a[i].y].m_adiac.push_back(&a[i]);
		b[a[i].y].adiac.push_back(&b[a[i].x]);
	}
	for (int i=0; i<n; i++)
	{
		b[i].dist=INF;
		b[i].bif=false;
		hp[i]=&b[i];
		b[i].hp_pos=i;
	}
	hplen=n; //no createhp() because we ony have INF in the heap
	int sum=0;
	for (int i=0; i<n; i++)
	{
		nod * nd = hpextractmax();
		nd->bif=true;
		std::list<nod*>::iterator i;
		std::list<muchie*>::iterator mch;
		muchie * min = NULL;
		for ((i=nd->adiac.begin()),(mch=nd->m_adiac.begin());i!=nd->adiac.end();(i++),(mch++))
		{
			if ((*i)->bif)
			{
				if ((!min)||(min->c>(*mch)->c))
					min=(*mch);
			} else {
				if ((*mch)->c<(*i)->dist)
				{
					(*i)->dist=(*mch)->c;
					hpup((*i)->hp_pos);
				}
			}

		}
		if (min)
		{
			sum+=min->c;
			min->bif=true;
		}
		
	}
	
	fprintf(fout, "%d\n%d\n",sum,n-1);
	for (int i=0; i<m; i++)
		if (a[i].bif)
			fprintf(fout, "%d %d\n", a[i].x+1, a[i].y+1);
	fclose(fin);
	fclose(fout);
    return 0;
}