//

//#pragma GCC optimize ("Ofast")
//#pragma GCC optimize ("fast-math")
//#pragma GCC optimize ("unroll-loops")
//#define _USE_MATH_DEFINES

#include <iostream>
#include <fstream>
//#include <vector>
//#include <cstring>
//#include <cmath>
//#include <bitset>
#include <queue>
//#include <stack>
//#include <utility>
//#include <algorithm>
//#include <string>
//#include <map>
//#include <unordered_map>
//#include <set>
//#include <unordered_set>
//#include <cstdint>
//#include <climits>
//#include <iomanip>
//#include <cstdio>
//#include <tuple>

using namespace std;

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

const int NRMAX = 200000;

struct Nod 
{
	int cost;
	int from;
	int to; 

	bool operator>(const Nod& other) const 
	{
		return cost > other.cost;
	}
};

struct Muchie 
{
	int to;
	int cost;
};

vector<Muchie> gr[NRMAX + 1];
bool b[NRMAX + 1];

int main()
{
	//ios_base::sync_with_stdio(false);
	//cin.tie(nullptr);
	//cout.tie(nullptr);

	priority_queue<Nod, vector<Nod>, greater<Nod>> pq;
	vector<pair<int, int>> rez;

	int n, m, rezc = 0;

	fin >> n >> m;
	for (int i = 1; i <= m; ++i)
	{
		int x, y, d;
		fin >> x >> y >> d;
		gr[x].push_back({ y, d });
		gr[y].push_back({ x, d });
	}

	pq.push({ 0, 1, 1 });

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

		int to = cur.to;
		int from = cur.from;
		if (b[to] == true)
			continue;
		b[to] = true;

		rezc += cur.cost;

		if (to != from)
			rez.emplace_back(from, to);

		for (const auto& it : gr[to])
			if (b[it.to] == false)
				pq.push({ it.cost, to, it.to });
	}

	fout << rezc << "\n";
	fout << rez.size() << "\n";
	for (const auto& it : rez)
		fout << it.first << " " << it.second << "\n";

	return 0;
}