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

struct muchie
{
    int x;
    int y;
    int cost;
} G[400005], sol[200005];
int tata[NMAX], h[NMAX];
int minim, maxim, num, n, m, p, nr_minim;
int cost_minim;


void citire();
void krushk();
int Find(int x2);
void Union(int x, int y);
void Heap_Combination(int i, int n);
void creation();
muchie extract(int &n);

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

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

void krushk()
{
    int i, nr;
    int x2, y2;
    nr=0;
    muchie minim;
    for(i=1;i<=n-1;i++)
    {
        minim=extract(m);
		x2=Find(minim.x);
		y2=Find(minim.y);
        if(x2!=y2)
        {
            cost_minim+=minim.cost;
			Union(x2,y2);
			sol[i]=minim;
        }
        else
            i--;
    }
    printf("%d\n", cost_minim);
    printf("%d\n", n-1);
    for(i=1;i<=n-1;i++)
	printf("%d %d\n", sol[i].x , sol[i].y);
}

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]++;
	}
}

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

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

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