#include <fstream>
#include <iostream>
#include <climits>
#include <algorithm>
#include <vector>
#include <cstring>

using namespace std;

#define INF INT_MAX
#define maxN 200005
#define PB push_back
#define MKP make_pair

int N , M , cost[maxN] , tata[maxN];
bool viz[maxN];

vector < pair <int , int> > lista[maxN] , sol;

int main ()
{
	ifstream f ("apm.in");
	ofstream g ("apm.out");
	
	f >> N >> M;
	
	int a , b , c;
	
	for (int i = 1 ; i <= M ; ++i)
	{
		f >> a >> b >> c;
		
		lista[a].PB (MKP (b , c));
		lista[b].PB (MKP (a , c));
	}
	
	
	for (int i = 2 ; i <= N ; ++i)
		cost[i] = INF;
	
	cost[1] = 0;
	
	int min_cost , nod , sol_cost = 0;
	
	for (int t = 1 ; t <= N ; ++t)
	{
		min_cost = INF;
		
		for (int i = 1 ; i <= N ; ++i)
			if (cost[i] < min_cost && !viz[i])
			{
				min_cost = cost[i];
				nod = i;
			}
		
		sol.PB (MKP (nod , tata[nod]));
		viz[nod] = true;
		
		sol_cost += min_cost;
		
		for (unsigned int i = 0 ; i < lista[nod].size () ; ++i)
		{
			int nodcur = lista[nod][i].first;
			int costcur = lista[nod][i].second;
			
			if (cost[nodcur] <= costcur || viz[nodcur])
				continue;
			
			cost[nodcur] = costcur;
			tata[nodcur] = nod;
		}
	}
	
	g << sol_cost << "\n" << sol.size () - 1 << "\n";
	
	for (unsigned int i = 1 ; i < sol.size () ; ++i)
		g << sol[i].first << " " << sol[i].second << "\n";
	
	return 0;
}