#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;




typedef struct Node {
	int source;
	int dest;
	int length;
}Node;

vector<vector<Node>> vect;
vector<Node> result;
vector<bool> visited;

struct compFunc{
	bool operator()(Node &a, Node &b) {
		return a.length > b.length;
	}
};

void Kruskal(int start) {
	priority_queue<Node, vector<Node>, compFunc> q;

	for (int i = 0; i < vect[start].size(); i++) {
		q.push(vect[start][i]);
	}

	visited[start] = true;
	while (!q.empty()) {

		Node n = q.top(); q.pop();

		
		if (!visited[n.dest])
		{
			visited[n.dest] = true;
			result.push_back(n);
			for (int i = 0; i < vect[n.dest].size(); i++) {
				if (!visited[vect[n.dest][i].dest])
					q.push(vect[n.dest][i]);
			}
		}
	}
}


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

	int n, m;
	scanf("%d %d", &n, &m);

	vect.resize(n+1);
	visited.resize(n+1);

	for (int i = 1; i <= m; i++) {
		int x, y, length;

		scanf("%d %d %d", &x, &y, &length);
		Node n;
		n.source = x;
		n.dest = y;
		n.length = length;
		vect[x].push_back(n);
		swap(n.dest, n.source);
		vect[y].push_back(n);
	}

	Kruskal(1);

	int sum = 0;
	for (int i = 0; i < result.size(); i++) {
		sum += result[i].length;
	}
	printf("%d\n%d\n", sum, result.size());
	for (int i = 0; i < result.size(); i++) {
		printf("%d %d\n", result[i].source, result[i].dest);
	}

	return 0;
}