#include <fstream>
#include <queue>
#include <vector>

using namespace std;

const int nmax = 200000;

struct GRAF {
	int x, y, c;
	bool operator < (GRAF other) const {
		return c > other.c;
	}
};

struct MUCHIE {
	int x, y;
};

priority_queue <GRAF> q;
int t[nmax + 1], h[nmax + 1];
vector <MUCHIE> sol;

void init(int n) {
	for(int i = 1; i <= n; ++ i) {
		t[i] = i;
		h[i] = 1;
	}
}

int tata(int x) {
	while(t[x] != x) {
		x = t[x];
	}
	return x;
}

int reuniune(int x, int y) {
	if(h[x] >= h[y]) {
		t[y] = x;
		if(h[x] == h[y]) {
			++ h[x];
		}
	} else {
		t[x] = y;
	}
}

int main() {
    ifstream fin("apm.in");

    int n, m;
    fin >> n >> m;
    for(int i = 1; i <= m; ++ i) {
    	int x, y, c;
    	fin >> x >> y >> c;
    	q.push({x, y, c});
    }

    fin.close();

    init(n);

    int rasp = 0;
    while(!q.empty()) {
    	if(tata(q.top().x) != tata(q.top().y)) {
    		reuniune(tata(q.top().x), tata(q.top().y));
    		rasp += q.top().c;
    		sol.push_back({q.top().x, q.top().y});
    	}
    	q.pop();
    }

    ofstream fout("apm.out");

    fout << rasp << '\n';
    fout << sol.size() << '\n';

    for(int i = 0; i < sol.size(); ++ i) {
    	fout << sol[i].x << " " << sol[i].y << '\n';
    }

    fout.close();

    return 0;
}