#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<int> father;
vector<int> sizee;
int n,m;

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

int findRoot(int x){
	if(x == father[x])
		return x;
	return x = findRoot(father[x]);
}

int main(){
	fin >> n >> m;
	father.resize(n+1);
	sizee.resize(n+1);
	for(int i = 0; i < n; ++i){
		father[i] = i;
		sizee[i] = 1;
	}
	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(findRoot(x) != findRoot(y) && sizee[findRoot(x)] < sizee[findRoot(y)]){
			int mulX = findRoot(x);
			int mulY = findRoot(y);
			father[mulX] = mulY;
			sizee[mulY] += sizee[mulX];
			taken.push_back({x,y,z});
		}
		else if(findRoot(x) != findRoot(y)){
			int mulX = findRoot(x);
			int mulY = findRoot(y);
			father[mulY] = mulX;
			sizee[mulX] += sizee[mulY];
			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';
	}
}