# include <iostream>
# include <fstream>
# include <vector>
# include <queue>
# include <stdio.h>
# include <climits>
# include <algorithm>


# define INPUT_FILE_NAME "apm.in"
# define OUTPUT_FILE_NAME "apm.out"
# define N_MAX 200000
# define PII std::pair<int, int>

struct Graph {
	int n, m;
	std::vector<PII> a[N_MAX];
};

struct Compare {
	bool operator()(PII const &l, PII const &r) {
		return l.second > r.second;
	}
};

Graph *g = new Graph();
std::vector<PII> mst;
int mst_cost = 0;

void read_graph() {
	std::fstream fin(INPUT_FILE_NAME, std::ios::in);
	fin >> g->n >> g->m;
	int src, dest, cost;
	while(fin >> src >> dest >> cost) {
		g->a[src].push_back(PII(dest, cost));
		g->a[dest].push_back(PII(src, cost));
	}
	fin.close();
}

std::ostream& operator<<(std::ostream &stream, Graph *g) {
	stream << "N = "<< g->n << " M = " << g->m << '\n';
	for (int i = 1; i <= g->n; i++) {
		stream << i << ": ";
		for (std::vector<PII>::iterator it = g->a[i].begin(); it != g->a[i].end(); it++) {
			stream << it->first << " (cost " << it->second << "); ";
		}
		stream << '\n';
	}
	return stream;
}


void print_mst () {
	std::fstream fout(OUTPUT_FILE_NAME, std::ios::out);
	fout << mst_cost << "\n" << mst.size() << "\n";
	for (unsigned int i = 0; i < mst.size(); i++) {
		fout << mst[i].first << " " << mst[i].second << "\n";
	}
	fout.close();
}

void prim() {
	std::priority_queue<PII, std::vector<PII>, Compare> pq;
	int p[N_MAX], d[N_MAX];
	bool viz[N_MAX];
	int s = 1;
	for(int i = 1 ; i <= g->n; i++) {
		p[i] = 0;
		d[i] = INT_MAX;
		viz[i] = false;
	}
	d[s] = 0;
	pq.push(PII(s, d[s]));
	int nod, cost, sw = true;
	while(!pq.empty()) {
		nod = pq.top().first;
		cost= pq.top().second;
		pq.pop();
		while(viz[nod]) {
			if(pq.empty()) {
				sw = false;
				break;
			}
			nod = pq.top().first;
			cost= pq.top().second;
			pq.pop();
		}
		if(!sw) break;
		mst.push_back(PII(nod, p[nod]));
		mst_cost += cost;
		viz[nod] = true;
		for(std::vector<PII>::iterator it = g->a[nod].begin(); it < g->a[nod].end(); it++) {
			if(!viz[it->first] && d[it->first] > it->second) {
				d[it->first] =  it->second;
				p[it->first] = nod;
				pq.push(PII(it->first, it->second));
			}
		}
	}

	// sterg din ama perechea (sursa, 0)
	std::vector< PII >::iterator it;
  	it = std::find (mst.begin(), mst.end(), PII(s, 0));
  	if (it != mst.end()) {
  	  	mst.erase (it);
  	}
}


int main(void) {
	read_graph();
	// std::cout << g;
	prim();
	print_mst();
	return 0;
}