#include <ctime>
#include <cstdlib>

#include <algorithm>
#include <fstream>
#include <vector>
using namespace std;

#define int64 long long
#define fi first
#define se second

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

const int kMaxN = 200005;


class Edge {
  public :
	int a, b, c;
	Edge() {
		a = b = c = 0;
	}
	Edge(int _a, int _b, int _c) {
		a = _a;
		b = _b;
		c = _c;
	}
	bool operator < (const Edge &rhs) const {
		return c < rhs.c;
	}
};  

class Dst { // disjoint-set data
  private:
	int father[kMaxN]; 
	int get_father(int nod);
  public:
  	Dst() {
		for (int i = 0; i < kMaxN; ++i)
			father[i] = i;
	}
	bool join(Edge E);
	bool join(int a, int b);
} P;

int Dst::get_father(int nod) {
	if (nod != father[nod])
		father[nod] = get_father(father[nod]);
	return father[nod];
}

bool Dst::join(int a, int b) {
 	a = get_father(a);
	b = get_father(b);

	if (a == b)
		return false;
	
	int r = rand() % 2;
	if (r)
		swap(a, b);
	father[a] = b;
	return true;
}

bool Dst::join(Edge E) {
	int a = E.a;
	int b = E.b;
 	return join(a, b);
}

vector<pair<int, int> > rez_edge; 
vector<Edge> edge;

int main() {
	int n, m;
 	in >> n >> m;
	while (m--) {
		int a, b, t = 1;
    	in >> a >> b;
		if (a > b)
			swap(a, b);
		switch (t) {
		  case 0: {
		  	P.join(a, b);
		  }
		  
		  case 1: {
			int c;
			in >> c;
			edge.push_back(Edge(a, b, c));
		  }
		}
	}
	sort(edge.begin(), edge.end());
	int64 rez = 0;
	for (int i = 0; i < int(edge.size()); ++i) {
		if (P.join(edge[i])) {
			rez += edge[i].c;
			rez_edge.push_back(make_pair(edge[i].a, edge[i].b));
		}
	}
	sort(rez_edge.begin(), rez_edge.end());
	out << rez << '\n';
	out << rez_edge.size() << '\n';
	for (int i = 0; i < int(rez_edge.size()); ++i)
		out << rez_edge[i].fi << ' ' << rez_edge[i].se << '\n';
	return 0;
}