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

using namespace std;
const int MAXN = 2e5 + 5;
const int MAXM = 4e5 + 5;
struct muchie{
	int x, y, cost;
};
muchie M[MAXM];

int tip,x,y;

ifstream fin("apm.in");
ofstream fout("apm.out");
int t[MAXN],n,m,h[MAXN];
vector < pair < int ,int > > ans;
bool cmp(muchie x, muchie y) {
	return x.cost < y.cost;
}

int findroot(int nod) {
	if(t[nod] == nod)
		return nod;
	return t[nod] = findroot(t[nod]);
}

void Union(int rad1, int rad2) {
	if(h[rad1] > h[rad2]) {
		t[rad2] = rad1;
}
else
	if(h[rad1] < h[rad2]) {
		t[rad1] = rad2;
}
else // daca au aceeasi inaltime
{
	t[rad1] = rad2;
	h[rad2]++;
}

}

int main() {
	fin >> n >> m;
	for (int i = 1; i <= n; ++i) {
		t[i] = i;
		h[i] = 1;
}
	for ( int i = 1; i <= m; ++i){
	fin >> M[i].x >> M[i].y >> M[i].cost;
}
	sort(M+1,M+m+1,cmp);
	long long s = 0;
	for ( int i = 1; i <= m; ++i) {
		if(findroot(M[i].x) != findroot(M[i].y)) {
			Union(findroot(M[i].x),findroot(M[i].y));
			s+=M[i].cost;
			ans.push_back({M[i].x,M[i].y});
}
}
	fout << s <<"\n"<< ans.size() <<"\n";
	for ( auto idk :  ans)
    fout << idk.second <<" "<< idk.first <<"\n";
}