#include <algorithm>
#include <stack>
#include <queue>
#include <deque>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <cstring>

using namespace std;

//#include <iostream>
#include <fstream>

//ifstream cin ("input.in");
//ofstream cout ("output.out");

ifstream cin ("apm.in");
ofstream cout ("apm.out");

static const int NMAX = 2e5+5;  

struct config {
	int x, y, cost;
};

class cmp {
public:
	const bool operator () ( const config &a, const config &b ) {
		return a.cost < b.cost;
	} 
};

int n, m;

int father[NMAX];
vector<pair <int, int>> ans;
config edge[2*NMAX];

int parent(int vertex) {
	if ( father[vertex] == vertex ) {
		return vertex;
	}

	father[vertex] = parent(father[vertex]);
	return father[vertex];
}

void unite (int a, int b) {
	father[parent(a)] = parent(b);
}

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

	cin>>n>>m;
	for ( int i = 1; i <= n; ++i ) {
		father[i] = i;
	}

	for ( int i = 1; i <= m; ++i ) {
		cin>>edge[i].x>>edge[i].y>>edge[i].cost;
	}

	sort (edge+1, edge+m+1, cmp());

	int sum = 0;
	int k = 0;

	for ( int i = 1; i <= m; ++i ) {
		if ( parent(edge[i].x) == parent(edge[i].y) ) {
			continue;
		}

		ans.push_back({edge[i].x, edge[i].y});
		unite(edge[i].x, edge[i].y);
		sum += edge[i].cost;
		k++;
	}

	cout<<sum<<'\n'<<k<<'\n';
	for ( auto x:ans ) {
		cout<<x.first<<" "<<x.second<<'\n';
	}
}