#include <bits/stdc++.h>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
struct edge {
	int x, y, c;
	bool operator <(edge a) const {
		return c > a.c;
	}
};
struct deseu {
	vector<int> parent;
	vector<int> sz;
	void build(int n) {
		parent = sz = vector<int>(n + 1);
	}
	void make_set(int x) {
		parent[x] = x;
		sz[x] = 1;
	}
	int find_set(int v) {
		if (v == parent[v]) {
			return v;
		}
		return parent[v] = find_set(parent[v]);
	}
	void unite(int a ,int b) {
		a = find_set(a);
		b = find_set(b);
		if (a != b) {
			if (sz[a] < sz[b]) {
				swap(a, b);
			}
			parent[b] = a;
			sz[a] += sz[b];
		}
	}
};
int main() {
	int n,m;
	fin >> n >> m;
	priority_queue<edge> pq;
	deseu tree;
	tree.build(n + 1);
	for (int i = 1; i <= n; ++i) {
		tree.make_set(i);
	}
	for (int i = 1; i <= m; ++i) {
		int x, y, c;
		fin >> x >> y >> c;
		pq.push({ x,y,c });
	}
	int cost = 0;
	vector <edge> sol;
	while (!pq.empty()) {
		edge top = pq.top();
		if (tree.find_set(top.x) != tree.find_set(top.y)) {
			tree.unite(top.x, top.y);
			cost += top.c;
			sol.push_back(top);
		}
		pq.pop();
	}
	fout << cost << '\n';
	fout << (int)sol.size() << '\n';
	for (auto i : sol) {
		fout << i.x << ' ' << i.y << '\n';
	}

}

/*#include <fstream>
#define NMAX 100005
using namespace std;

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

int n, m, type, x, y;
int Papa[NMAX], Rank[NMAX];

/*int Find(int a)
{
    int aux, b;
    for (aux = a; Papa[aux] != aux; aux = Papa[aux]);
    while (Papa[a] != a)
    {
        b = Papa[a];
        Papa[a] = aux;
        a = b;
    }
}

int main()
{
    in >> m;
    while (m)
    {
        in >> x >> y >> type;
        switch(type)
        {
            case 1:
                while (Papa[x]) x = Papa[x];
                while (Papa[y]) y = Papa[y];
                Papa[y] = x;
                break;
            case 2:
                while (Papa[x]) x = Papa[x];
                while (Papa[y]) y = Papa[y];
                if (x == y)
                    out << "DA" << '\n';
                    else
                    out << "NU" << '\n';
                break;
        }
        --m;
    }
    return 0;
}*/