#include<fstream>
#include<algorithm>
#define NMax 200005
#define MMax 400005
using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

struct Muchie
{
	int x,y,c;
};

int N,M,Cost,K;
int TT[NMax],R[NMax];
int Sol[MMax];
Muchie V[MMax];

bool Cmp(Muchie a,Muchie b)
{
	return (a.c < b.c);
}

void Read()
{
	fin>>N>>M;

	for(int i = 1 ; i <= M ; ++i)
	{
		fin>>V[i].x>>V[i].y>>V[i].c;
	}

    sort(V+1,V+M+1,Cmp);
}

int Father(int x)
{
    while(TT[x] != x)
		x = TT[x];

	return x;
}

void Unite(int x,int y)
{
	if(R[x] < R[y])	TT[x] = y;
	else	TT[y] = x;

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

void Solve()
{
	for(int i = 1 ; i <= N ; ++i)
		TT[i] = i;

	for(int i = 1 ; i <= M ; ++i)
	{
		if(Father(V[i].x) != Father(V[i].y))
		{
			Unite(V[i].x,V[i].y);
			Cost += V[i].c;
            Sol[++K] = i;
		}
	}
}

void Print()
{
	fout<<Cost<<"\n"<<N-1<<"\n";

	for(int i = 1 ; i <= K ; ++i)
		fout<<V[i].x<<" "<<V[i].y<<"\n";
}

int main()
{
	Read();
	Solve();
	Print();

	fin.close();
	fout.close();
	return 0;
}