#include <bits/stdc++.h>
using namespace std;

typedef pair<int,int> PII;
typedef pair<int,PII> PIII;

const int MAXN = 200005;

vector<PIII> G[MAXN], ans;
priority_queue<PIII, vector<PIII>, greater<PIII>> PQ;

int n, m, a, b, c;
long long sum;
bool viz[MAXN];

void Prim() {
	for(auto node : G[1])
		PQ.push(node);
		
	viz[1] = 1;
	for(int i = 1; i <= n - 1; i++) {
		while(viz[PQ.top().second.second])
			PQ.pop();
			
		auto curr = PQ.top();
		ans.push_back(curr);
		sum += curr.first;
		viz[curr.second.second] = 1;
		
		for(auto node : G[curr.second.second])
			if(viz[node.second.second] == 0)
				PQ.push(node);
	}
}

int main() {
	ifstream cin("apm.in");
	ofstream cout("apm.out");
	
	cin >> n >> m;
	for(int i = 1; i <= m; i++) {
		cin >> a >> b >> c;
		G[a].push_back({c, {a, b}});
		G[b].push_back({c, {b, a}});
	}
	
	Prim();
	
	cout << sum << "\n" << ans.size() << "\n";
	for(auto e : ans)
		cout << e.second.first << " " << e.second.second << "\n";
	
	return 0;
}