#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
using namespace std;

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

using VI = vector<int>;
using VVI = vector<VI>;
using VP = vector<pair<int, int>>;
using VVP = vector<VP>;
using VB = vector<bool>;

const int Inf = 0x3f3f3f3f;

struct Edge{
	int x, w;
	
	bool operator < (const Edge& e) const
	{
		return w > e.w;
	}
};

int N, M;		// N - nr. de noduri, M - nr. de muchii
VVP G;			// graful initial
VI t;			// t[i] = tata lui i in apm
VP apm;			// lista cu muchiile din apm
int cmin;		// costul minim pentru apm
VB vis;			// vis[i] = true <=> am vizitat nodul i
VI key;			// key[i] = cheia nodului i, adica cu ce cost de muchie il aduc in arbore

void ReadData();
void Prim(int node);
void WriteGraph();

int main()
{
	ReadData();
	Prim(1);
	
	WriteGraph();
	
	fin.close();
	fout.close();
	return 0;
}

void ReadData()
{
	fin >> N >> M;
	G = VVP(N + 1);
	t = VI(N + 1);
	key = VI(N + 1, Inf);
	vis = VB(N + 1);
	
	int x, y, w;
	while (M--)
	{
		fin >> x >> y >> w;
		
		G[x].push_back({y, w});
		G[y].push_back({x, w});
	}
}

void Prim(int node)
{
	priority_queue<Edge> Q;
	Q.push({node, 0});			// deoarece incep cu nodul node, il pun pe el in coada
	t[node] = -1;				// si ii atribui costul muchiei cu care a fost introdus ca fiind 0
	key[node] = 0;
	
	int x, y, w;
	while (!Q.empty())
	{
		x = Q.top().x;				// extrag primul nod din coada(care are si costul minim)
		vis[x] = true;				// il marchez ca vizitat
		
		if (t[x] != -1)						// daca are tata(deci nu e radacina apm-ului) pun 
			apm.push_back({t[x], x});		// in lista muchiilor apm-ului muchia de la t[x] la x
		cmin += Q.top().w;					// si adun si costul muchiei la costul apm-ului
		
		for (const auto& p : G[x])			// pt. fiecare vecin y al lui x
		{
			y = p.first;
			w = p.second;
			
			if (vis[y])						// daca a fost deja vizitat sar peste el
				continue;
			
			if (key[y] > w)					// daca muchia pe care ar introduce-o nodul x cu vecinul sau y
			{								// are costul mai mic decat ce am avut pana acum pt. y
				key[y] = w;					// modufic cheia lui y si pun perechea {y, key[y]} in coada
				Q.push({y, w});
				
				t[y] = x;					// aici retin tatal lui x
			}
		}
		
		while (!Q.empty() && vis[Q.top().x])		// in coada pot sa am noduri deja vizitate
			Q.pop();								// care trebuiesc sterse
	}
}

void WriteGraph()
{
	fout << cmin << '\n';
	fout << apm.size() << '\n';
	
	for (const auto& p : apm)
		fout << p.first << ' ' << p.second << '\n';
}