#include <queue>
#include <iostream>

using namespace std;

vector < vector < pair <int, int> > > G;
int N, M, cost;
bool visited[200005];


struct Edge {
	int x, y, c;
	Edge (int x, int y, int c) {
		this->x = x;
		this->y = y;
		this->c = c;
	}
};

vector <Edge> sol;

bool operator< (const Edge &e1, const Edge &e2) {
	return e1.c > e2.c;
}

void read () {
	cin >> N >> M;

	G.resize(N + 1);

	for (int i = 0; i < M; ++i) {
		int x, y, c;
		cin >> x >> y >> c;
		G[x].push_back(make_pair(y, c));
		G[y].push_back(make_pair(x, c));
	}
}

void prim (int current) {
	priority_queue <Edge> q;
	visited[current] = true;

	vector< pair <int, int> >::iterator it = G[current].begin();
	while (it != G[current].end()) {
		q.push(Edge(current, it->first, it->second));
		++it;
	}

	int nodes = 0;
	while (!q.empty()) {
		Edge e = q.top();		

		q.pop();

		if (visited[e.y])
			continue;

		visited[e.y] = true;
		cost += e.c;
		sol.push_back(e);
		++nodes;

		vector< pair <int, int> >::iterator it = G[e.y].begin();
		while (it != G[e.y].end()) {
			if (!visited[it->first])
				q.push(Edge(e.y, it->first, it->second));

			++it;
		}
	}
}

int main (void) {
	ios_base::sync_with_stdio(false);

	freopen("apm.in", "r", stdin);
	freopen("apm.out", "w", stdout);

	read();
	prim(1);

	cout << cost << "\n" << sol.size() << "\n";


	for (unsigned int i = 0; i < sol.size(); ++i) {
		cout << sol[i].x << " " << sol[i].y << "\n";
	}

	return 0;
}