#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);

	set < pair <int, int> > RB; // (cost, node)

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

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

		// add edge to mst
		pair <int, int> Find = *RB.begin();
		RB.erase(RB.begin());

		int minCost = Find.first;
		int addNode = Find.second;

		mstCost += minCost;
		used[addNode] = true;

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

				if(RB.count({connEdge[edge.first].second, edge.first}))
					RB.erase({connEdge[edge.first].second, edge.first});

				connEdge[edge.first] = {addNode, edge.second};
				RB.insert({edge.second, edge.first});
			}
	}

	fout << mstCost << '\n' << V - 1 << '\n';

	for(int node = 2; node <= V; ++node)
		fout << node << ' ' << connEdge[node].first << '\n';
}