#include <iostream>
#include <fstream>
#include <vector>
#include <list>
#include <algorithm>
#include <limits>

using namespace std;

#define NMAX 200001
#define MMAX 400001
#define INF  numeric_limits<int>::max()

int n, m;
list<pair<int, int>> adj_list[NMAX];
vector<pair<int, int>> mst;

int heap_size;
int heap[NMAX], pos[NMAX], v[NMAX], u[NMAX];

int parent(int x)
{
	return x / 2;
}

int left_child(int x)
{
	return x * 2;
}

int right_child(int x)
{
	return x * 2 + 1;
}

void sift(int x)
{
	int left, right, child = 0;

	while (x != child) {
		child = x;
		left = left_child(x);
		right = right_child(x);

		if (left <= heap_size && v[heap[x]] > v[heap[left]])
			x = left;
		if (right <= heap_size && v[heap[x]] > v[heap[right]])
			x = right;

		swap(heap[x], heap[child]);
		swap(pos[heap[x]], pos[heap[child]]);
	}
}

void percolate(int x)
{
	while (parent(x) && v[heap[x]] < v[heap[parent(x)]]) {
		swap(heap[x], heap[parent(x)]);
		swap(pos[heap[x]], pos[heap[parent(x)]]);
		x = parent(x);
	}
}

void insert_into_heap(int x)
{
	heap_size++;
	heap[heap_size] = x;
	pos[x] = heap_size;
	percolate(heap_size);
}

int pop_root_from_heap()
{
	int x = heap[1];
	pos[x] = 0;
	
	int y = heap[heap_size];
	heap[1] = y;
	pos[y] = 1;
	heap_size--;

	sift(1);

	return x;
}

void insert_into_mst(int x)
{
	for (auto e : adj_list[x]) {
		int y = e.first;
		int c = e.second;

		if (c < v[y]) {
			v[y] = c;
			u[y] = x;
		}
	}
}

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

	// read input
	int x, y, c;
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= m; i++) {
		scanf("%d%d%d", &x, &y, &c);
		adj_list[x].push_back({y, c});
		adj_list[y].push_back({x, c});
	}

	// initialize heap
	v[1] = 0;
	for (int i = 2; i <= n; i++)
		v[i] = INF;
	insert_into_mst(1);
	for (int i = 2; i <= n; i++)
		insert_into_heap(i);

	// main loop
	int sum = 0;
	for (int i = 2; i <= n; i++) {
		x = pop_root_from_heap();
		insert_into_mst(x);

		sum += v[x];
		mst.push_back({x, u[x]});

		// restore heap structure for neighbors
		for (auto e : adj_list[x]) {
			y = e.first;
			if (pos[y])
				percolate(pos[y]);
		}
	}

	// print output
	printf("%d\n%d\n", sum, n - 1);
	for (auto e : mst)
		printf("%d %d\n", e.first, e.second);

	return 0;
}