#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<=N-1;i++)
        for(int j=i+1;j<=N;j++)
        {
            if(Muche[i].cost>Muche[j].cost)
            {
            muchie aux=Muche[i];
            Muche[i]=Muche[j];
            Muche[j]=Muche[i];
            }
        }


	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 < N; i++)
	{
	    while(!ok)
        {
        x=Muche[t].left;
        y=Muche[t].right;

		if (caut(x)!=caut(y))
		{
			unite(caut(x),caut(y));
			Sum+=Muche[t].cost;
			ok=1;
			ArbSol[Soll++]=t;
        }
        else
            t++;
        }
        ok=0;
	}

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

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



	return 0;
}