#include <fstream>
#include <vector> 
#include <queue>

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


const int NMAX = 200001;

int N; int M;

std::vector< std::pair<int, int> > G[NMAX];

std::vector < std::pair<int, int> > Tree;


void read() {

	fin >> N >> M;

	for(int i = 1; i <= M; ++i) {

		int x; int y; int cost;
		fin >> x >> y >> cost;
		G[x].push_back(std::make_pair(y, cost));
		G[y].push_back(std::make_pair(x, cost));
	}
}

int Prim() {

	std::priority_queue < std::pair< int, int > , std::vector < std::pair < int, int > > , std::greater < std::pair < int, int > > > Q;

	int cost = 0;

	int start = 1;

	int viz[NMAX];

	int i;

	for(int i = 1; i <= N; ++i)
		viz[i] = 0;

	viz[start] = 1;

	for(unsigned i = 0 ; i < G[start].size(); ++i)
		Q.push(std::make_pair(G[start][i].second, G[start][i].first) );

	while(i < N - 1) {

		int node = Q.top().second;
		int ad_cost = Q.top().first;

		Q.pop();

		if(viz[node] == 1) continue;

		cost = cost + ad_cost;
		++i;

		for(unsigned j = 0 ;j < G[node].size(); ++j) {

			if( viz [ G[node][j].first ] == 1 && G[node][j].second == ad_cost) 
				Tree.push_back(std::make_pair(node, G[node][j].first) );

			if(viz [ G[node][j].first ] == 1) continue;



			Q.push(std::make_pair( G[node][j].second, G[node][j].first) );

		}

		viz[node] = 1;
	}

	return cost;
}

int main() {

	read();

	fout << Prim() << '\n';

	fout << N - 1 << '\n'; 

	for(int i = 0 ; i < N - 1; ++i)
		fout << Tree[i].first << " " << Tree[i].second << '\n';

	return 0;


}