#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <stack>
#include <list>

class Graph {
private:
	struct Edge {
		int x, y, cost;
		Edge(int x, int y, int cost = 0) : x(x), y(y), cost(cost) {}
	};

	struct Neighbour {
		int node, cost;
		Neighbour(int x, int cost = 0) : node(x), cost(cost) {}
	};

	std::vector<std::vector<Neighbour> >la;
	std::vector<std::vector<Neighbour> >li;
	std::vector<Edge> edges;

	const int N_NODES;
	const int N_EDGES;
	
	void KosarajuTopSortHelper(std::list<int>& nodes, int n, std::vector<bool>& used);
	void KosarajuAddToComponent(int n, std::vector<bool>& used, std::vector<int>& component);
public:
	Graph(int N, int M) : N_NODES(N), N_EDGES(M) { la.resize(N + 1); li.resize(N + 1); }
	void getInfo();
	void addEdge(int from, int to, int cost = 0,bool isDirected = 0);
	
	std::vector<int> BFS(int start); // distance from start vector
	int getComponentCount(); 
	std::vector<int> getTopologicalSort();
	std::vector<std::vector<int> > Kosaraju();

	std::pair<int, std::vector<int> > Prim();
	static bool HavelHakimi(const std::vector<int>& deg);
};

void Graph::addEdge(int from, int to, int cost, bool isDirected) {
	la[from].push_back({ to, cost });
	li[to].push_back({ from, cost });
	edges.push_back({ from, to, cost });

	if (!isDirected) {
		la[to].push_back({ from, cost });
		li[from].push_back({ to, cost });
	}
}

std::vector<int> Graph::BFS(int start) {
	std::vector<int> dist(N_NODES + 1, -1);
	dist[start] = 0;

	std::queue<int> q;
	q.push(start);

	while (!q.empty()) {
		int top = q.front();
		q.pop();

		for (const Neighbour& x : la[top]) {
			if (dist[x.node] == -1) {
				dist[x.node] = dist[top] + 1;
				q.push(x.node);
			}
		}
	}
	return std::vector<int>(dist.begin() + 1, dist.end());
}

int Graph::getComponentCount() {
	std::stack<int> st;
	std::vector<bool> used(N_NODES + 1, false);
	int count = 0;
	
	for (int i = 1; i <= N_NODES; ++i) {
		if (!used[i]) {
			count++;

			// DFS
			st.push(i);
			while (!st.empty()) {
				int top = st.top();
				st.pop();
				used[top] = 1;
				
				for (const Neighbour& n : la[top])
					if (!used[n.node]) st.push(n.node);
			}
		}
	}

	return count;
}

void Graph::getInfo() {
	std::cout << "N: " << N_NODES << '\n';
	std::cout << "M: " << N_EDGES << '\n';
	for (int i = 1; i <= N_NODES; ++i) {
		std::cout << i << ": ";
		for (const Neighbour& x : la[i]) {
			std::cout << "(" << x.node << ", " << x.cost << ") ";
		}
		std::cout << '\n';
	}

	std::cout << "Edges: \n";
	for (const Edge& m : edges) {
		std::cout << m.x << " " << m.y << " " << m.cost << '\n';
	}
}

std::vector<int> Graph::getTopologicalSort() {
	std::vector<int> in_deg(N_NODES + 1, 0);
	std::vector<int> result;
	result.reserve(N_NODES);

	for (int i = 1; i <= N_NODES; ++i) {
		for (const Neighbour& x : la[i]) {
			in_deg[x.node]++;
		}
	}

	std::queue<int> q;
	for (int i = 1; i <= N_NODES; ++i) {
		if (in_deg[i] == 0)q.push(i);
	}

	while (!q.empty()) {
		int n = q.front();
		q.pop();

		result.push_back(n);
		for (const Neighbour& x : la[n]) {
			in_deg[x.node]--;
			if (in_deg[x.node] == 0) {
				q.push(x.node);
			}
		}
	}
	return result.size() == N_NODES ? result : std::vector<int>(); // if cycle => empty
}

void Graph::KosarajuTopSortHelper(std::list<int>& nodes, int n, std::vector<bool>& used) {
	used[n] = 1;
	for (const Neighbour& x : la[n]) {
		if (!used[x.node])KosarajuTopSortHelper(nodes, x.node, used);
	}
	nodes.push_front(n);
}

void Graph::KosarajuAddToComponent(int n, std::vector<bool>& used, std::vector <int>&comp) {
	comp.push_back(n);
	used[n] = 1;

	for (const Neighbour& x : li[n]) {
		if (!used[x.node])
			KosarajuAddToComponent(x.node, used, comp);
	}
}

std::vector<std::vector<int> > Graph::Kosaraju(){
	
	// part 1 (topological sort-ish)
	std::list<int> nodes;
	std::vector<bool> used(N_NODES + 1, false);
	for (int i = 1; i <= N_NODES; ++i) {
		if (!used[i])
			KosarajuTopSortHelper(nodes, i, used);
	}
	
	// part 2
	std::fill(used.begin(), used.end(), false);
	std::vector<std::vector<int> > result;

	for (int n : nodes) {
		if (!used[n]) {
			std::vector<int> component;
			KosarajuAddToComponent(n, used, component);
			result.push_back(component);
		}
	}

	return result;
}

bool Graph::HavelHakimi(const std::vector<int>& deg) {
	std::list<int> degrees;

	int sum = 0;
	int N = deg.size();
	for (int i : deg) {
		sum += i;
		if (i >= N)return false; // max deg = N - 1
		degrees.push_back(i);
	}
	
	if (sum & 1)return false; // M = sum deg / 2
	if (sum / 2 > N * (N - 1) / 2)return false; // M <= N * (N-1) / 2

	degrees.sort([](int x, int y) { return x > y; });

	while (!degrees.empty()) {
		int d = degrees.front();
		degrees.pop_front();

		for (int& i : degrees) {
			if (d == 0)break;
			if (i - 1 < 0) return false;
			i--;
			d--;
		}
		degrees.sort([](int x, int y) { return x > y; });
	}

	return 1;
}

std::pair<int, std::vector<int> > Graph::Prim() {
	std::vector<int> cost(N_NODES + 1, 1e9);
	std::vector<bool> used(N_NODES + 1, false);
	std::vector<int> parent(N_NODES + 1, -1);

	struct Compare {
		bool operator()(const Neighbour& a, const Neighbour& b) { return a.cost > b.cost; }
	};

	std::priority_queue<Neighbour, std::vector<Neighbour>, Compare> pq;

	cost[1] = 0;
	int cmin = 0;
	pq.push({ 1, 0 });

	while (!pq.empty()) {
		int n = pq.top().node;
		pq.pop();
		if (used[n])continue;

		used[n] = 1;
		cmin += cost[n];

		for (const Neighbour& x : la[n]) {
			if (!used[x.node] && x.cost < cost[x.node]) {
				cost[x.node] = x.cost;
				parent[x.node] = n;
				pq.push({ x.node, cost[x.node] });
			}
		}
	}
	return { cmin, parent };
}

void print(const std::vector<int>& x) {
	for (int i : x) {
		std::cout << i << ' ';
	}
	std::cout << '\n';
}

int main(){

	std::ifstream f("apm.in");
	std::ofstream g("apm.out");

	int N = 0, M = 0;
	f >> N >> M;
	 
	Graph a(N, M);

	for (int i = 0; i < M; ++i) {
		int x, y, c;
		f >> x >> y >> c;

		a.addEdge(x, y, c);
	}
 
	auto res = a.Prim();

	g << res.first << '\n' << res.second.size() - 2 << '\n';
	for (int i = 2; i <= res.second.size() - 1; ++i) {
		g << i << ' ' << res.second[i] << '\n';
	}
}