#include <cstdio>
#define NMAX 200005
using namespace std;

struct muchie
	{
    int x;
    int y;
    int cost;
	};
	
muchie G[400005];

int tata[NMAX], h[NMAX];
int minim, maxim, num, n, m, p, nr_minim;
int cost_minim;

muchie extragemin(int &n);
void combinare(int i, int n);
void citire();
void kruskal();
int Find(int x2);
void Union(int x, int y);
void creation();

muchie sol[200005];
int completat;

int main()
	{
	freopen("apm.in","r",stdin);
	freopen("apm.out","w",stdout);
    citire();
	creation();
    kruskal();
    return 0;
	}

muchie extragemin(int &n)
	{
	muchie x=G[1];
	G[1]=G[n];n--;
	combinare(1, n);
	return x;
	}

void citire()
	{
    int i, x, y, c;
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++)
		{
        scanf("%d%d%d",&x,&y,&c);
		G[i].x=x;G[i].y=y;G[i].cost=c;
		}
	}

void kruskal()
	{
	int i;
	muchie rez;
	int c1, c2;
	for (i=1;i<=n-1;i++)
		{
		rez=extragemin(m);
		c1=Find(rez.x);
		c2=Find(rez.y);
		if (c1!=c2)
			{
			cost_minim+=rez.cost;
			sol[completat]=rez;
			completat++;
			Union(c1, c2);
			}
		else i--;
		}
	printf("%d\n", cost_minim);
	printf("%d\n", n-1);
	for (i=0;i<completat;i++)
		printf("%d %d \n", sol[i].x, sol[i].y);
	}

void combinare(int i, int n)
	{
	int fiu, tata, x;
	muchie aux;
	tata=i;
	fiu=2*i;
	x=G[i].cost;
	aux=G[i];
	while (fiu<=n)
		{
		if (fiu+1<=n)
		fiu=G[fiu].cost>G[fiu+1].cost?fiu+1:fiu;
		if (x>G[fiu].cost)
			{
			G[tata]=G[fiu];
			tata=fiu; 
			fiu=2*tata;
			}
		else break;
		}
	G[tata]=aux;
	}

void creation() 
	{
	int i;
	for(i=m/2;i>=1;i--)
		combinare(i, n);
	}

int Find(int x2)
{
	int rad;
	int aux;
	rad=x2;
	while(tata[rad])
		rad=tata[rad];
	aux=x2;
	while(tata[x2])
	{
		aux=x2;
		x2=tata[x2];
		tata[aux]=rad;
	}
	return rad;
}

void Union(int x,int y)
{
	if(h[x]>h[y])
		tata[y]=x;
	else
	{
		tata[x]=y;
		if(h[x]==h[y])
            h[y]++;
	}
}