#include <iostream>
#include <cstdio>
#include <fstream>
#include <set>
#include <vector>
#include <list>
#include <queue>
#include <algorithm>
#include <stack>

#define inf 2000000000

using namespace std;

int n, m, k, costArobre;

class edge {
public:
	int a, b, cost;
	edge() {}
	edge(int x, int y, int c) {
		a = x;
		b = y;
		cost = c;
	}
};

class compEdges {
public:
	bool operator ()(const edge& lhs, const edge& rhs) {
		return lhs.cost > rhs.cost;
	}
};

vector<priority_queue<edge, vector<edge>, compEdges> > tree;
bool visited[200001];

vector<edge> edges;
vector<int> visitedVerticies;
set<int> unvisited;

int main()
{
	int i, j, a, b, c, currentVertex, selectedVertex, minVertexVal, vertex;
	edge minEdge;
	priority_queue<edge, vector<edge>, compEdges >currentQueue;
	edge currentEdge;
	freopen("apm.in", "r", stdin);
	freopen("apm.out", "w", stdout);
	scanf("%d %d", &n, &m);
	tree.resize(n);
	for (i = 1; i < n; i++) unvisited.insert(i);
	for (i = 1; i <= m; i++) scanf("%d%d%d", &a, &b, &c), tree[a - 1].push(*new edge(a - 1, b - 1, c)), tree[b - 1].push(*new edge(b - 1, a - 1, c));
	currentVertex = 0;
	visitedVerticies.push_back(0);
	visited[0] = true;
	while (!unvisited.empty()) {
		selectedVertex = 0;
		minEdge.cost = inf;
		for (vector<int>::iterator it = visitedVerticies.begin(); it != visitedVerticies.end(); it++) {
			vertex = *it;
			while (!tree[vertex].empty() && visited[tree[vertex].top().b]) tree[vertex].pop();
			if (!tree[vertex].empty() && tree[vertex].top().cost < minEdge.cost && !visited[tree[vertex].top().b]) {
				selectedVertex = vertex;
				minEdge = tree[vertex].top();
			}
		}

		visited[minEdge.b] = visited[minEdge.a] = true;
		edges.push_back(minEdge);
		costArobre += minEdge.cost;
		visitedVerticies.push_back(minEdge.b);
		tree[selectedVertex].pop();
		unvisited.erase(minEdge.b);
	}
	printf("%d\n", costArobre);
	printf("%d\n", edges.size());
	for (edge e : edges) printf("%d %d %d\n", e.a + 1, e.b + 1, e.cost);

	return 0;
}