#include <bits/stdc++.h>

using namespace std;

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

vector < vector < pair <int, int> > > adjList;
int V, E;

int main(){

	fin >> V >> E;

	adjList.resize(V + 1);

	for(int e = 0; e < E; ++e){

		int u, v, c;
		fin >> u >> v >> c;

		adjList[u].push_back({v, c});
		adjList[v].push_back({u, c});
	}

	vector < pair <int, int> > connEdge(V + 1, {0, INT_MAX}); // minimal connection edge
	vector <bool> used(V + 1);

	used[1] = true;
	for(pair <int, int> &edge : adjList[1])
		connEdge[edge.first] = {1, edge.second};

	vector < pair <int, int> > mstEdges;
	mstEdges.reserve(E);

	int mstCost = 0;
	for(int it = 1; it < V; ++it){

		// add edge to mst
		int minCost = INT_MAX;
		int addNode = -1;
		for(int node = 1; node <= V; ++node) // find minimum
			if(!used[node] and connEdge[node].second < minCost)
				addNode = node, minCost = connEdge[node].second;

		mstCost += minCost;
		mstEdges.push_back({addNode, connEdge[addNode].first});
		used[addNode] = true;

		for(pair <int, int> &edge : adjList[addNode])
			if(!used[edge.first] and edge.second < connEdge[edge.first].second)
				connEdge[edge.first] = {addNode, edge.second};
	}

	fout << mstCost << '\n' << mstEdges.size() << '\n';

	for(int i = 0; i < (int)mstEdges.size(); ++i)
		fout << mstEdges[i].first << ' ' << mstEdges[i].second << '\n';
}