#include <bits/stdc++.h>
#include <tuple>

using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

struct iii{
	int x,y,z;
};

vector<iii> edges;
vector<iii> taken;
vector<vector <int> > multimi;
vector<int> multime;
int n,m;

bool cmp(iii a, iii b){
	return a.z < b.z;
}

int main(){
	fin >> n >> m;
	multimi.resize(n+1);
	multime.resize(n+1);
	for(int i = 0; i < n; ++i){
		multimi[i].push_back(i);
		multime[i] = i;
	}
	for(int i = 0; i < m; ++i){
		int a,b,c;
		fin >> a >> b >> c;
		a--;
		b--;
		edges.push_back({a,b,c});
	}

	sort(edges.begin(), edges.end(), cmp);

	for(int i = 0; i < m; ++i){
		int x = edges[i].x;
		int y = edges[i].y;
		int z = edges[i].z;
		if(multime[x] != multime[y]){
			int mulX = multime[x], mulY = multime[y];
			while(multimi[mulY].size()){
				int f = multimi[mulY].back();
				multime[f] = mulX;
				multimi[mulX].push_back(f);
				multimi[mulY].pop_back();
			}
			taken.push_back({x,y,z});
		}
	}
	int r = 0;
	for(int i = 0; i < taken.size(); ++i){
		r += taken[i].z;
	}
	fout << r << '\n';
	fout << taken.size() << '\n';
	for(int i = 0; i < taken.size(); ++i){
		fout << taken[i].y + 1 <<' '<< taken[i].x + 1<< '\n';
	}
}