#include <fstream>
#include <queue>
#include <vector>

#define NMax 200010
#define INF 1000000000

using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

int nodes, edges, lowestCostEdge[NMax], tCost, nE;
bool mark[NMax];

struct Edge {
	int father;
	int node;
	int cost;

	Edge() {}
	Edge(int _f, int _n, int _c) {
		this->father = _f;
		this->node = _n;
		this->cost = _c;
	}
};
vector < pair<int, int> > G[NMax], answ;

class cmp {
public:
	bool operator()(const Edge& p1, const Edge& p2) {
		return p1.cost > p2.cost;
	}
};
priority_queue<Edge, vector< Edge >, cmp> H;

void Prim(int source)
{
	for (int i = 1; i <= nodes; i++)
		lowestCostEdge[i] = INF;
	lowestCostEdge[source] = 0;

	H.push(Edge(0, source, 0));

	while (!H.empty() && nE < nodes - 1) {
		while (!H.empty() && mark[H.top().node] == true)
			H.pop();
		if (H.empty())
			break;

		Edge crt = H.top();
		H.pop();
		mark[crt.node] = true;

		if (crt.node != source) {
			nE++;
			tCost += crt.cost;
			answ.push_back(make_pair(crt.father, crt.node));
		}

		for (auto &edge : G[crt.node]) {
			if (!mark[edge.first] && lowestCostEdge[edge.first] > edge.second) {
				lowestCostEdge[edge.first] = edge.second;
				H.push(Edge(crt.node, edge.first, lowestCostEdge[edge.first]));
			}
		}
	}
}

int main()
{
	f >> nodes >> edges;
	int n1, n2, cost;
	for (int i = 1; i <= edges; i++) {
		f >> n1 >> n2 >> cost;
		G[n1].push_back(make_pair(n2, cost));
		G[n2].push_back(make_pair(n1, cost));
	}

	Prim(1);

	g << tCost << '\n';
	g << nE << '\n';
	for (auto ans : answ) {
		g << ans.first << ' ' << ans.second << '\n';
	}
}