#include <fstream>
#include <queue>
#include <cstring>
#define INF 0x3f3f3f3f
using namespace std;
const char iname[] = "apm.in";
const char oname[] = "apm.out";
ifstream fin(iname);
ofstream fout(oname);
int N , M , x , y , i , j , nrN , cost_arbore=0;
int T[ 200004 ];
bool viz[ 200004 ];
int D[ 200004 ];
struct nod {
	int vf , cost;
};
vector < nod > v[ 200004 ];
struct cmp {
	bool operator() ( const nod &a , const nod &b ) const
	{
		return a.cost > b.cost;
	}
};
priority_queue < nod , vector < nod > , cmp > Q;
int main()
{
	fin >> N >> M;
	nod arb;
	for ( i = 1; i <= M; ++i )
	{
		fin >> x >> arb.vf >> arb.cost;
		v[ x ].push_back( arb );
		y = arb.vf;		arb.vf = x;
		v[ y ].push_back( arb );
	}
	nrN = N;
	memset ( D , INF , sizeof( D ) );
	D[ 0 ] = 0; D[ 1 ] = 0;
	nod start;  
	start.vf = 1; start.cost = 0;
	Q.push( start );
	viz[ 0 ] = 1;
	vector < nod > :: iterator it;
	while( nrN )
	{
		x = 0;
		while ( viz[ x ] )
		{
			x = Q.top().vf;
			Q.pop();
		}
		viz[ x ] = 1;
		cost_arbore += D[ x ];
		nrN--;
		for ( it = v[ x ].begin(); it != v[ x ].end(); ++it )
		{
			if ( D[ it -> vf ] > it -> cost && viz[ it -> vf ] == 0 )
			{
				T[ it -> vf ] = x;
				D[ it -> vf ] = it -> cost;
				nod arb; 
				arb.vf = it -> vf; 
				arb.cost = it -> cost;
				Q.push( arb );
			}
		}
	}
	fout << cost_arbore << '\n' << N - 1 << '\n';
	for ( i = 2; i <= N; ++i ) 
		fout << i << ' ' << T[ i ] << '\n';
	return 0;
}