#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;

#define NMAX 200001
#define MMAX 400001
#define pb push_back
#define mp make_pair
#define cost first
#define n1 second.first
#define n2 second.second

pair< int, pair< int, int > > Muchii[MMAX];
vector< pair< int, int > > Sol;
int N, M, i, Cost;
int Pd[NMAX];

inline int Grup( int Nod )
{
	if( Pd[Nod] != Nod ) Pd[Nod] = Grup( Pd[Nod] );
	return Pd[Nod];
}

int main()
{
	freopen("apm.in", "r", stdin);
	freopen("apm.out", "w", stdout);
	
	scanf("%d%d", &N, &M );
	for( i = 0; i < M; ++i )
		scanf("%d%d%d", &Muchii[i].n1, &Muchii[i].n2, &Muchii[i].cost );
	sort( Muchii, Muchii + M );
	for( i = 1; i <= N; ++i )
		Pd[i] = i;
	
	for( i = Cost = 0; i < M; ++i )
	{
		int P1 = Grup( Muchii[i].n1 ), P2 = Grup( Muchii[i].n2 );
		
		if( P1 != P2 )
		{
			Pd[P1] = Pd[P2];
			Cost += Muchii[i].cost;
			Sol.pb( Muchii[i].second );
		}
	}
	
	printf("%d\n%d\n", Cost, N - 1 );
	for( vector< pair< int, int > >::iterator it = Sol.begin(); it != Sol.end(); ++it )
		printf("%d %d\n", (*it).first, (*it).second );
	
	return 0;
}