#include <cstdio>
#include <algorithm>

#define NMAX 200020

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

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


}Muche[400005];

bool comp(muchie& a,muchie& b)
{
    return a.cost<b.cost;
}

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


    std::sort (Muche+1, Muche+M+1,comp);

    for(int i=1;i<=M;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;
	}


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