#include <algorithm>
#include <cmath>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <vector>
#include <fstream>
#include <cstring>
using namespace std;

#define fast_io ios::sync_with_stdio(0); cin.tie(0); do{}while(0)
typedef long long ll;

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

const int MAXN = 2e5 + 5;
const int INF = 0x3f3f3f3f;

struct Edge {
	int src, dest, c;

	bool operator <(const Edge& other) const {
		return c > other.c;
	}
};

int n, m;
vector<Edge> graph[MAXN];
priority_queue<Edge> h;
int distances[MAXN];
bool visited[MAXN];

vector<Edge> edges;

void ReadData() {
	fin >> n >> m;
	int a, b, c;
	for (int i = 0; i < m; i++) {
		fin >> a >> b >> c;
		graph[a].push_back({a, b, c});
		graph[b].push_back({b, a, c});
	}
}

void Prim(int start) {
	h.push({0, start, 0});

	while (!h.empty()) {
		Edge curr = h.top();
		h.pop();

		if (visited[curr.dest]) {
			continue;
		}
		visited[curr.dest] = true;

		if (curr.src != 0) {
			edges.push_back(curr);
		}

		for (Edge next : graph[curr.dest]) {
			if (visited[next.dest]) {
				continue;
			}
			h.push({curr.dest, next.dest, next.c});
		}
	}

	int cost = 0;
	for (Edge e : edges) {
		cost += e.c;
	}
	fout << cost << '\n';
	fout << edges.size() << '\n';
	for (Edge e : edges) {
		fout << e.src << ' ' << e.dest << '\n';
	}
	fout << '\n';
}

void Solve() {
	Prim(1);
}

int main() {
		ReadData();
		Solve();
		return 0;
}