#include <iostream>
#include <fstream>
#include <queue>
#include <utility>
#include <tuple>

using namespace std;

const int N = 200001;

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

int n, m, start, cost_total, nrm_arb;

vector<pair<int, int>> adj[N];

vector<pair<int, int>> muchii;

priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> pq;

bool viz[N];

int main()
{
	bool primul = false;
	fin >> n >> m;
	//cout << "n: " << n << '\n';
	//cout << "m: " << m << '\n';
	for (int i = 1; i <= m; ++i)
	{
		int u, v, cost;
		fin >> u >> v >> cost;
		//cout << "read u: " << u << '\n';
		//cout << "read v: " << v << '\n';
		//cout << "read cost: " << cost << '\n';
		if (!primul)
		{
			start = u;
			primul = true;
		}
		adj[u].push_back({v, cost});
		adj[v].push_back({u, cost});
	}
	//cout << "start: " << start << '\n';
	for (auto [u, cost] : adj[start])
	{
		//cout << "u: " << u << '\n';
		//cout << "cost u: " << cost << '\n';
	}
	pq.push({0, start, -1});
	while (!pq.empty())
	{
		auto [cost, nod, parinte] = pq.top();
		//cout << "cost: " << cost << '\n';
		//cout << "nod: " << nod << '\n';
		//cout << "parinte: " << parinte << '\n';
		pq.pop();
		if (viz[nod]) continue;
		viz[nod] = true;
		cost_total += cost;
		if (parinte != -1)
		{
			muchii.push_back({parinte, nod});
			++nrm_arb;
		}
		for (auto [v, cost] : adj[nod])
		{
			//cout << "v: " << v << '\n';
			//cout << "cost v: " << cost << '\n';
			if (!viz[v])
			{
				pq.push({cost, v, nod});
			}
		}
	}
	fout << cost_total << '\n';
	fout << nrm_arb << '\n';
	for (auto [u, v] : muchii)
	{
		fout << u << ' ' << v << '\n';
	}
	fin.close();
	fout.close();
	return 0;
}