#include <cstdio>
#include <cstdlib>
#include <list>
#define INF 0x3f3f3f3f
using namespace std;

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

typedef struct
{
	int dest,c;
} muchie;

typedef struct
{
	int x,y;
} muchie_rel;

typedef struct
{
	list<muchie> adiac;
	int dist,hp_pos;
	bool sel;
} nod;

nod a[200000];
int hp[200000];
muchie_rel rez[200000];
int hpn;

inline bool hp_lesser(int v1, int v2)
{
	return (a[hp[v1]].dist<a[hp[v2]].dist);
}

inline void hp_swap(int v1, int v2)
{
	hp[v1]=hp[v1]^hp[v2];
	hp[v2]=hp[v1]^hp[v2];
	hp[v1]=hp[v1]^hp[v2];
	a[hp[v1]].hp_pos=v1;
	a[hp[v2]].hp_pos=v2;
}

void hp_up(int i)
{
	while (i)
	{
		int pos=((i+1)>>1)-1;
		if (hp_lesser(i,pos))
			hp_swap(i,pos);
		else 
			break;
		i=pos;
	}
}

void hp_down(int i)
{
	while (1)
	{
		int p1=(i<<1)+1;
		int p2=(i<<1)+2;
		int min=i;
		if ((p1<hpn)&&hp_lesser(p1,min))
			min=p1;
		if ((p2<hpn)&&hp_lesser(p2,min))
			min=p2;
		if (min!=i)
			hp_swap(min,i);
		else 
			break;
		i=min;
	}
}

int hp_popmin()
{
	int min=hp[0];
	hp_swap(0,--hpn);
	hp_down(0);
	return min;
}

int main (int argc, char * const argv[]) {
	int n,m;
	fscanf(fin, "%d %d",&n,&m);
	for (int i=0; i<m; i++)
	{
		int x,y,c;
		fscanf(fin, "%d %d %d", &x,&y,&c);
		x--; y--;
		muchie tmp;
		tmp.c=c;
		tmp.dest=y;
		a[x].adiac.push_back(tmp);
		tmp.dest=x;
		a[y].adiac.push_back(tmp);
	}
	for (int i=0; i<n; i++)
	{
		a[i].dist=INF;
		a[i].hp_pos=i;
		a[i].sel=false;
		hp[i]=i;
	}
	hpn=n; //no hp_create because the while heap is INF
	int sum=0;
	for (int in=0; in<n; in++)
	{
		int vf = hp_popmin();
		a[vf].sel=true;
		muchie min;
		min.c=INF;
		min.dest=-1;
		list<muchie>::iterator i;
		for (i=a[vf].adiac.begin(); i!=a[vf].adiac.end(); i++)
		{
			if (a[i->dest].sel)
			{
				if ((i->c)<min.c)
				{
					min.c=i->c;
					min.dest=i->dest;
				}
			} else {
				if ((i->c)<a[i->dest].dist)
				{
					a[i->dest].dist=i->c;
					hp_up(a[i->dest].hp_pos);
				}
			}
		}
		if (min.dest!=-1)
		{
			rez[in].x=vf;
			rez[in].y=min.dest;
			sum+=min.c;
		}
	}
	fprintf(fout, "%d\n%d\n",sum,n-1);
	for (int i=1; i<n; i++)
		fprintf(fout, "%d %d\n",rez[i].x+1,rez[i].y+1);
	fclose(fin);
	fclose(fout);
    return 0;
}