#include<fstream>
#include<cstdio>
#include<algorithm>

using namespace std;

const int MaxN = 200001;
const int MaxM = 400001;

const char InFile[] = "apm.in";
const char OutFile[] = "apm.out";

int N,M,cost,T[MaxN],R[MaxN],sol[MaxN];
struct edge
{
	int x,y,cost;
};
edge E[MaxM];

bool cmp( edge X , edge Y )
{
	return X.cost < Y.cost;
}

int find(int x)
{
	int rad,y;
	rad = x;
	while( T[rad] != rad )
		rad = T[rad];
	while( T[x] != x )
		{
			y = T[x];
			T[x] = rad;
			x = y;
		}
	return rad;
}

void unire(int x,int y)
{
	if( R[x] <= R[y] )
		T[x] = y;
		else
		T[y] = x;
	if( R[x] == R[y] )
		++R[y];
}

int main()
{
	ifstream fin( InFile );
	ofstream fout( OutFile );
	fin >> N >> M;
	int i;
	for( i = 1 ; i <= M ; ++i )
		fin >> E[i].x >> E[i].y >> E[i].cost;
	for( i = 1 ; i <= N ; ++i )
		{
			T[i] = i;
			R[i] = 1;
		}
	sort(E+1,E+M+1,cmp);
	int nrm,rx,ry;
	for( i = 1 , nrm = 0 , cost = 0 ; nrm < N-1 ; ++i )
		{
			rx = find(E[i].x);
			ry = find(E[i].y);
			if( rx != ry )
				{
					cost += E[i].cost;
					sol[++nrm] = i;
					unire(rx,ry);
				}
		}
	fout << cost << '\n' << nrm << '\n';
	for( i = 1 ; i < N ; ++i )
		fout << E[sol[i]].x << ' ' << E[sol[i]].y << '\n';
	fin.close();
	fout.close();
	return 0;
}