#include <iostream>
	#include <algorithm>
	#include <fstream>
	#include <vector>
	#include <queue>
	using namespace std;
	int n, m, x, y, c, rez, nr;
	pair <int,int> rez2[200005];
	vector <pair<int, int>> v[200005];
	bool inapm[200005];
	priority_queue<pair<int, pair<int,int>>> q;
	ifstream fin("apm.in");
	ofstream fout("apm.out");
	int main() {
		fin >> n >> m;
		for (int i = 1; i <= m; i++) {
			fin >> x >> y >> c;
			v[y].push_back({ x,c });
			v[x].push_back({ y,c });
		}
		q.push({ 0,{1,1}});
		while (!q.empty()) {
			pair<int, pair<int,int>> top = q.top();
			q.pop();
			int cost = -top.first;
			int nod = top.second.second;
			if (inapm[nod]) continue;
			rez += cost;
			nr++;
			rez2[nr] = { top.second.first,top.second.second };
			inapm[nod] = 1;
			for (auto el : v[nod]) {
				if (!inapm[el.first]) q.push({ -el.second,{nod,el.first} });
			}
		}
		fout << rez << "\n" << nr-1 << "\n";
		for (int i = 2; i <= nr; i++)
			fout << rez2[i].first << " " << rez2[i].second << "\n";
	}