#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define ld long double
#define endl "\n"
 
const int Nmax = 100010;
const int MODULO = 1e9 + 7;
const int oo = -1e9;

vector < tuple < int , int, int > > muchii;

int n, m;
int rang[Nmax], tata[Nmax];
int cost = 0;
vector < pair < int , int > > sol;


int findDaddy(int nod) {
	while(tata[nod] != nod) {
		nod = tata[nod];
	}
	return nod;
}

void uniune(int x, int y) {
	if(rang[x] < rang[y]) {
		tata[x] = y;
	}
	if(rang[x] > rang[y]) {
		tata[y] = x;
	}

	if(rang[x] == rang[y]) {
		tata[x] = y;
		rang[y]++;
	}
}

void solve() {
	cin >> n >> m;
	for(int i = 1; i <= m; i++) {
		int x, y, c; cin >> x >> y >> c;
		muchii.push_back({c, x, y});
		muchii.push_back({c, y, x});
	}
	sort(muchii.begin(), muchii.end());
	for(int i = 1; i <= n; i++) {
		rang[i] = 1;
		tata[i] = i;
	}

	for(auto it : muchii) {
		int x = findDaddy(get<1>(it));
		int y = findDaddy(get<2>(it));
		if(x != y) {
			uniune(x, y);
			sol.push_back({get<1>(it), get<2>(it)});
			cost += get<0>(it);
		}
	}

	cout << cost << endl;
	cout << sol.size() << endl;
	for(auto it : sol) {
		cout << it.first << " " << it.second << endl;
	}
}
	
void fisier() {
	freopen("apm.in" , "r", stdin);
	freopen("apm.out", "w", stdout);
}

 
int main() {
	ios_base::sync_with_stdio(0);
 
	cin .tie(0);
	cout.tie(0);

	fisier();
 
	int testCases = 1;
	//cin >> testCases;
	while(testCases--) {
		solve();
	}
}