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

#define NMax 100010
#define INF 2000000000

using namespace std;

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

int nodes, edges, sum, cnt, d[NMax];
bool mark[NMax];
vector< pair<int, int> > G[NMax];
pair<int, int> apmEdg[NMax];

struct hElem {
	int father;
	int node;
	int cost;
};

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

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

	H.push(hElem{ 0, node, 0 });

	while (!H.empty() && cnt < nodes) {

		int crtNode = H.top().node;
		int edgeCost = H.top().cost;
		int crtFather = H.top().father;
		H.pop();

		if (crtNode != node && !mark[crtNode]) {
			sum += edgeCost;

			++cnt;
			apmEdg[cnt].first = crtFather;
			apmEdg[cnt].second = crtNode;
		}

		mark[crtNode] = true;

		for (vector < pair<int, int> >::iterator it = G[crtNode].begin(); it != G[crtNode].end(); it++) {
			if (!mark[it->first] && d[it->first] > it->second) {
				d[it->first] = it->second;
				H.push(hElem{ crtNode, it->first, it->second });
			}
		}
	}

	g << sum << "\n";
	g << nodes - 1 << "\n";
	for (int i = 1; i <= nodes - 1; i++)
		g << apmEdg[i].first << " " << apmEdg[i].second << "\n";
}

int main()
{
	f >> nodes >> edges;

	int n1, n2, c;
	for (int i = 1; i <= edges; i++) {
		f >> n1 >> n2 >> c;

		G[n1].push_back(make_pair(n2 ,c));
		G[n2].push_back(make_pair(n1, c));
	}

	Prim(1);

	return 0;
}