#include<cstdio>
#include<fstream>
#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,sol[MaxN],T[MaxN],R[MaxN];
struct muchie {
		int x,y,cost;
		};
muchie E[MaxM];

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

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

void merge(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 <= n ; i++ )
		T[i] = i , R[i] = 1;
	for( i = 1 ; i <= m ; i++ )
		fin >> E[i].x >> E[i].y >> E[i].cost;
	fin.close();
	sort( E+1,E+m+1,cmp);
	int cost,nrm;
	for( i = 1,cost = 0,nrm = 0 ; nrm < n-1 ; i++ )
		{
			int rx,ry;
			rx = find_root(E[i].x);
			ry = find_root(E[i].y);
			if( rx != ry )
				{
					sol[++nrm] = i;
					merge(rx,ry);
					cost += E[i].cost;
				}
		}
	fout << cost << '\n' << nrm << '\n';
	for( i = 1 ; i < n ; i++ )
		fout << E[sol[i]].x << ' ' << E[sol[i]].y << '\n';
	fout.close();
	return 0;
}