#include <bits/stdc++.h>
#define NMAX 200010
#define inf (1 << 30)

using namespace std;


typedef tuple<int, int> edge;
#define get_cost(t) std::get<0>(t) 
#define get_neighbour(t) std::get<1>(t)



int n, m, cost_apm, root;
int dist[NMAX], parent[NMAX];
vector<edge> G[NMAX];
vector<edge> apm;
priority_queue<edge, vector<edge>, std::greater<edge>> pq;
bitset<NMAX> used;

void read_input() {
	ifstream fin("apm.in");

	fin >> n >> m;

	for (int i = 1; i <= m; ++i) {
		int x, y, c;
		fin >> x >> y >> c;

		G[x].push_back(edge(c, y));
		G[y].push_back(edge(c, x));
	}

	fin.close();
}

void Prim() {
	for (int i = 1; i <= n; ++i) {
		dist[i] = inf;
		parent[i] = 0;
	}

	root = 1;
	dist[root] = 0;
	parent[root] = 0;

	pq.push(edge(dist[root], root));

	cost_apm = 0;

	for (int i = 1; i <= n; ++i) {
        std::tuple<int, int> e;
        int node;

        do {
	        e = pq.top();
	        pq.pop();
	 
	        node = get_neighbour(e);
        } while (used[node]);
 
        cost_apm += dist[node];
        used[node] = 1;
 
        for (auto it = G[node].begin(); it != G[node].end(); ++it) {
            int neighbour = get_neighbour(*it), cost = get_cost(*it);
 
            if (!used[neighbour] && cost < dist[neighbour]) {
                dist[neighbour] = cost;
                parent[neighbour] = node;
                pq.push(edge(dist[neighbour], neighbour));
            }
        }
    }
}

void print_output() {
	ofstream fout("apm.out");

	fout << cost_apm << "\n";
	fout << (n - 1) << "\n";

	for (int i = 1; i <= n; ++i) {
		if (i != root) {
			fout << i << " " << parent[i] << "\n";
		}
	}

	fout.close();
}



int main() {
	read_input();
	Prim();
	print_output();

	return 0;
}