#include <cstdio>

#define NMAX 200020

int Tati[NMAX], Arb[NMAX];
int N, M;

struct muchie
{
    int cost;
    int left;
    int right;

}Muche[400005];

int ArbSol[NMAX];
int Soll=0;



int caut(int x)
{
	int R, y;


	for (R = x; Tati[R] != R; R = Tati[R]);


	for (; Tati[x] != x;)
	{
		y = Tati[x];
		Tati[x] = R;
		x = y;
	}
	return R;
}

void unite(int x, int y)
{

	if (Arb[x] > Arb[y])
		Tati[y] = x;
			else Tati[x] = y;


	if (Arb[x] == Arb[y]) Arb[y]++;
}

int main()
{
	freopen("apm.in", "r", stdin);
	freopen("apm.out", "w", stdout);

	scanf("%d %d ", &N, &M);

	for(int i=1;i<=M;i++)
    {
        int a,b,c;
        scanf("%d %d %d",&a,&b,&c);

        if(a>b)
            a^=b^=a^=b;
        Muche[i].cost=c;
        Muche[i].left=a;
        Muche[i].right=b;
    }

    for(int i=1;i<=M-1;i++)
        for(int j=i+1;j<=M;j++)
        {
            if(Muche[i].cost>Muche[j].cost)
            {
            muchie aux=Muche[i];
            Muche[i]=Muche[j];
            Muche[j]=aux;
            }
        }

    /*for(int i=1;i<=N;i++)
    {
        printf("%d ",Muche[i].cost);
    }
    printf("\n");
    */


	int i, x, y, Sum=0;

	for (i = 1; i <= N; i++)
	{
		Tati[i] = i;
		Arb[i] = 1;
	}

    int t=0;
    int ok=0;

	for (i = 1; i <= M; i++)
	{
        x=Muche[i].left;
        y=Muche[i].right;

		if (caut(x)!=caut(y))
		{
			unite(caut(x),caut(y));
			Sum+=Muche[i].cost;
			ArbSol[Soll++]=i;
        }
        else
            continue;

	}

	printf("%d\n%d\n",Sum,N-1);

	for(int i=0;i<Soll;i++)
    {
        printf("%d %d\n",Muche[ArbSol[i]].left,Muche[ArbSol[i]].right);
    }



	return 0;
}