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

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

struct Edge{
	int u, v, wt;
	bool operator < (const Edge &e) const{
		return wt < e.wt;
	}
};

vector <Edge> edges, ans;

int parent[200001], rang[200001];
int N, M;

int find_set(int v){
	if(v == parent[v])
		return v;
	return parent[v] = find_set(parent[v]);
}

void union_sets(int a, int b){
	a = find_set(a);
	b = find_set(b);
	if(a != b){
		if(rang[a] < rang[b])
			swap(a, b);
		parent[b] = a;
		if(rang[a] == rang[b])
			rang[a]++;
	}
}

void Kruskal(){
	int cost = 0;
	sort(edges.begin(), edges.end());

	for(Edge e : edges)
		if(find_set(e.u) != find_set(e.v)){
			cost += e.wt;
			ans.emplace_back(e);
			union_sets(e.u, e.v);
		}

	g << cost << "\n" << ans.size() << "\n";
	for(Edge e : ans){ 
		g << e.u << " " << e.v << "\n";
	}	
}

int main(){

	f >> N >> M;
	for(int i = 1;i <= N;i++)
		parent[i] = i, rang[i] = 0;

	while(M--){
		Edge e;
		f >> e.u >> e.v >> e.wt;
		edges.emplace_back(e);
	}

	Kruskal();

}