//1_a Kruskal
/*
#include <iostream>
#include <fstream>
#include <vector>
#include <tuple>
#include <algorithm>

using namespace std;

const int NMAX = 1e5;

int tata[NMAX + 1];
int inaltime[NMAX + 1];

//functie de initializare
void init(int n) {
	for (int i = 1; i <= n; i++) {
		tata[i] = i;
		inaltime[i] = 0;
	}
}

//functie de gasire reprezentant
int find(int x) {
	if (tata[x] != x) {
		tata[x] = find(tata[x]);
	}
	return tata[x];
}

//functie de unire a doua componente
void unire(int x, int y) {
	int rx = find(x);
	int ry = find(y);

	if (rx != ry) {
		if (inaltime[rx] > inaltime[ry]) {
			tata[ry] = rx;
		}
		else if (inaltime[rx] < inaltime[ry]) {
			tata[rx] = ry;
		}
		else {
			tata[ry] = rx;
			inaltime[rx]++;
		}
	}
}

int main()
{
	ifstream in("apm.in");
	ofstream out("apm.out");


	int n, m;
	in >> n >> m;

	vector <tuple<int, int, int>> muchii;

	for (int i = 0; i < m; i++ ) {
		int u, v, cost;
		in >> u >> v >> cost;
		muchii.emplace_back(cost, u, v);
	}

	sort(muchii.begin(), muchii.end());

	init(n);

	int apm_cost = 0;
	vector<pair<int, int>> apm_muchii;

	//Kruskal
	for (auto [cost, u, v] : muchii) {
		if (find(u) != find(v)) {
			unire(u, v);          
			apm_cost += cost;
			apm_muchii.emplace_back(u, v); 
		}
	}

	out << apm_cost << endl;
	out << apm_muchii.size()<< endl;
	for (auto [u, v] : apm_muchii) {
		out << u << " " << v << endl;
	}

	in.close();
	out.close();

	return 0;

}
//complexitate O(mlogn)
*/

//1_b Kruskal cu 3 muchii impuse(care sa nu formeze ciclu)
/*
#include <iostream>
#include <fstream>
#include <vector>
#include <tuple>
#include <algorithm>

using namespace std;

const int NMAX = 1e5;

int tata[NMAX + 1];
int inaltime[NMAX + 1];

//functie de initializare
void init(int n) {
	for (int i = 1; i <= n; i++) {
		tata[i] = i;
		inaltime[i] = 0;
	}
}

//functie de gasire reprezentant
int find(int x) {
	if (tata[x] != x) {
		tata[x] = find(tata[x]);
	}
	return tata[x];
}

//functie de unire a doua componente
void unire(int x, int y) {
	int rx = find(x);
	int ry = find(y);

	if (rx != ry) {
		if (inaltime[rx] > inaltime[ry]) {
			tata[ry] = rx;
		}
		else if (inaltime[rx] < inaltime[ry]) {
			tata[rx] = ry;
		}
		else {
			tata[ry] = rx;
			inaltime[rx]++;
		}
	}
}

int main()
{
	ifstream in("apm.in");
	ofstream out("apm.out");


	int n, m;
	in >> n >> m;

	vector <tuple<int, int, int>> muchii;

	for (int i = 0; i < m; i++) {
		int u, v, cost;
		in >> u >> v >> cost;
		muchii.emplace_back(cost, u, v);
	}

	vector<tuple<int, int, int>> muchii_obligatorii;
	for (int i = 0; i < 3; i++) {
		int u, v, cost;
		in >> u >> v >> cost;
		muchii_obligatorii.emplace_back(cost, u, v);
	}

	sort(muchii.begin(), muchii.end());

	init(n);

	int apm_cost = 0;
	vector<pair<int, int>> apm_muchii;

	//Kruskal
	for (auto [cost, u, v] : muchii_obligatorii) {
		if (find(u) != find(v)) {
			unire(u, v);
			apm_cost += cost;
			apm_muchii.emplace_back(u, v);
		}
		else {
			cout << "Nu exista un arbore valid. Cele 3 muchii obligatorii formeaza un ciclu." << endl;
			return 0;
		}
	}

	for (auto [cost, u, v] : muchii) {
		if (find(u) != find(v)) {
			unire(u, v);
			apm_cost += cost;
			apm_muchii.emplace_back(u, v);
		}
	}

	if (apm_muchii.size() != n - 1) {
		cout << "Nu exista un arbore valid care să includa cele 3 muchii obligatorii." << endl;
		return 0;
	}

	out << apm_cost << endl;
	out << apm_muchii.size() << endl;
	for (auto [u, v] : apm_muchii) {
		out << u << " " << v << endl;
	}

	in.close();
	out.close();

	return 0;
}
//aceeasi complexitate O(mlogn)
*/

//2 Prim
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <limits>

using namespace std;

const int NMAX = 1e5;
const int INF = numeric_limits<int>::max();

vector<pair<int, int>> L[NMAX + 1]; // Lista de adiacenta (vecin, cost)

// Structura pentru Min-Heap (cost, nod_curent, nod_vecin)
struct Muchie {
	int cost;
	int nod_curent;
	int nod_vecin;

	// Comparator pentru Min-Heap
	bool operator>(const Muchie& other) const {
		return cost > other.cost;
	}
};

int prim(int n, vector<pair<int, int>>& apm_muchii) {
	vector<bool> in_apm(n + 1, false); // Noduri incluse în APCM
	priority_queue<Muchie, vector<Muchie>, greater<Muchie>> pq; // Min-Heap

	int apm_cost = 0;

	// Începem de la nodul 1
	in_apm[1] = true;
	for (auto [vecin, cost] : L[1]) {
		pq.push({ cost, 1, vecin });
	}

	while (!pq.empty()) {
		Muchie top = pq.top();
		pq.pop();

		int cost = top.cost;
		int nod_curent = top.nod_curent;
		int nod_vecin = top.nod_vecin;

		if (in_apm[nod_vecin]) {
			continue; // Sărim peste muchiile care duc spre noduri deja incluse
		}

		// Adăugăm muchia în APCM
		in_apm[nod_vecin] = true;
		apm_cost += cost;
		apm_muchii.emplace_back(nod_curent, nod_vecin);

		// Adăugăm vecinii nodului vecin în Min-Heap
		for (auto [vecin, muchie_cost] : L[nod_vecin]) {
			if (!in_apm[vecin]) {
				pq.push({ muchie_cost, nod_vecin, vecin });
			}
		}
	}

	return apm_cost;
}

int main() {
	ifstream in("apm.in");
	ofstream out("apm.out");

	int n, m;
	in >> n >> m;

	for (int i = 0; i < m; i++) {
		int u, v, cost;
		in >> u >> v >> cost;
		L[u].emplace_back(v, cost);
		L[v].emplace_back(u, cost);
	}

	vector<pair<int, int>> apm_muchii;
	int apm_cost = prim(n, apm_muchii);

	// Afișăm rezultatele
	out << apm_cost << endl;
	out << apm_muchii.size() << endl;
	for (auto [u, v] : apm_muchii) {
		out << u << " " << v << endl;
	}

	return 0;
}