#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <climits>

using namespace std;

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


struct muchie
{
	int x, y, z;
};

struct compare {
	bool operator()(muchie a, muchie b)
	{
		return a.z > b.z;
	}
};

vector<pair<int, int>> sol;
vector<pair<int, int>> graf[200005];
priority_queue<muchie, vector<muchie>, compare> parcurgere;
int viz[200005];
int n, m;
int sum = 0;

void bfs(int nod)
{
	parcurgere.push({ 0, 1, INT_MAX });
	while (!parcurgere.empty() && sol.size() < n - 1)
	{
		while (viz[parcurgere.top().y] == 1)
		{
			parcurgere.pop();
		}
		int cNod = parcurgere.top().y, cost = parcurgere.top().z;
		viz[cNod] = 1;
		if (cNod != 1)
		{
			sol.push_back({ parcurgere.top().x, parcurgere.top().y });
			sum += cost;
		}
		parcurgere.pop();
		for (int i = 0; i < graf[cNod].size(); i++)
		{
			if (viz[graf[cNod][i].second] == 0)
			{
				parcurgere.push({ cNod, graf[cNod][i].second, graf[cNod][i].first });
			}
		}
	}
}

int main()
{
	fin >> n >> m;
	int x, y, z;
	for (int i = 0; i < m; i++)
	{
		fin >> x >> y >> z;
		graf[x].push_back({ z, y });
		graf[y].push_back({ z, x });
	}
	bfs(1);
	fout << sum << '\n' << sol.size() << '\n';
	for (int i = 0; i < sol.size(); i++)
	{
		fout << sol[i].first << ' ' << sol[i].second << '\n';
	}
}