#include <fstream>
#include <queue>

using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");

const int MAXN = 200002;
const int MAXM = 400004;
int n, m;

int ap[MAXN];
int suma = 0;

struct edge {
	int x, y, cost;
};
vector<edge> graph[MAXN];

struct comp {
	bool operator() (edge a, edge b){
		return a.cost > b.cost;
	}
};
priority_queue< edge, vector<edge>, comp> heap;

vector<edge> sol;

void adaug(int nod) {
	for (edge e : graph[n]) {
		if(!ap[e.y])
			heap.push(e);
	}
}

void solve() {
	ap[1] = 1;
	adaug(1);
	int suma = 0;
	while (sol.size() != n - 1) {
		edge e = heap.top();
		heap.pop();
		if (ap[e.y] == 0) {
			ap[e.y] = 1;
			adaug(e.y);
			sol.push_back(e);
			suma += e.cost;
		}
	}
}

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

		graph[x].push_back({ x,y,c });
	}

	fout << suma << "\n" << sol.size() << "\n";
	for (edge e : sol) {
		fout << e.x << " " << e.y << "\n";
	}
	return 0;
}