#include <bits/stdc++.h>

using namespace std;

struct Node { // Splay tree. Root's pp contains tree's parent.
	Node *p = 0, *pp = 0, *c[2];
	bool flip = 0;
	Node() { c[0] = c[1] = 0; Fix(); }
	void Fix() {
		if (c[0]) c[0]->p = this;
		if (c[1]) c[1]->p = this;
		// (+ update sum of subtree elements etc. if wanted)
	}
	void push_flip() {
		if (!flip) return;
		flip = 0; swap(c[0], c[1]);
		if (c[0]) c[0]->flip ^= 1;
		if (c[1]) c[1]->flip ^= 1;
	}
	int up() { return p ? p->c[1] == this : -1; }
	void rot(int i, int b) {
		int h = i ^ b;
		Node *x = c[i], *y = b == 2 ? x : x->c[h], *z = b ? y : x;
		if ((y->p = p)) p->c[up()] = y;
		c[i] = z->c[i ^ 1];
		if (b < 2) {
			x->c[h] = y->c[h ^ 1];
			z->c[h ^ 1] = b ? x : this;
		}
		y->c[i ^ 1] = b ? this : x;
		Fix(); x->Fix(); y->Fix();
		if (p) p->Fix();
		swap(pp, y->pp);
	}
	void Splay() { /// Splay this up to the root. Always finishes without flip set.
		for (push_flip(); p; ) {
			if (p->p) p->p->push_flip();
			p->push_flip(); push_flip();
			int c1 = up(), c2 = p->up();
			if (c2 == -1) p->rot(c1, 2);
			else p->p->rot(c2, c1 != c2);
		}
	}
	Node* first() { /// Return the min element of the subtree rooted at this, splayed to the top.
		push_flip();
		return c[0] ? c[0]->first() : (Splay(), this);
	}
};

struct LinkCut {
	vector<Node> T;
	LinkCut(int n) : T(n) {}

	void Link(int u, int v) { // add an edge (u, v)
		assert(!Connected(u, v));
		MakeRoot(&T[u]);
		T[u].pp = &T[v];
	}

	void Cut(int u, int v) { // remove an edge (u, v)
		Node *x = &T[u], *top = &T[v];
		MakeRoot(top); x->Splay();
		assert(top == (x->pp ?: x->c[0]));
		if (x->pp) x->pp = nullptr;
		else {
			x->c[0] = top->p = nullptr;
			x->Fix();
		}
	}

	bool Connected(int u, int v) { // are u, v in the same tree?
		Node* nu = Access(&T[u])->first();
		return nu == Access(&T[v])->first();
	}

	/// Move u to root of represented tree.
	void MakeRoot(Node* u) {
		Access(u);
		u->Splay();
		if(u->c[0]) {
			u->c[0]->p = 0;
			u->c[0]->flip ^= 1;
			u->c[0]->pp = u;
			u->c[0] = 0;
			u->Fix();
		}
	}

	/// Move u to root aux tree. Return the root of the root aux tree.
	Node* Access(Node* u) {
		u->Splay();
		while (Node* pp = u->pp) {
			pp->Splay(); u->pp = 0;
			if (pp->c[1]) {
				pp->c[1]->p = 0; pp->c[1]->pp = pp; }
			pp->c[1] = u; pp->Fix(); u = pp;
		}
		return u;
	}
};

int main() {
    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);
    ios_base::sync_with_stdio(false);

    int n, m; cin >> n >> m;
    LinkCut lk(n);

    vector<tuple<int, int, int>> Edges;
    for (int i = 0; i < m; ++i) {
        int a, b, c; cin >> a >> b >> c;
        Edges.emplace_back(c, a - 1, b - 1);
    }

    sort(Edges.begin(), Edges.end());

    int ans = 0;
    vector<pair<int, int>> sol;
    for (auto x : Edges) {
        int c, a, b;
        tie(c, a, b) = x;

        if (!lk.Connected(a, b)) {
            ans += c;
            sol.emplace_back(a + 1, b + 1);
            lk.Link(a, b);
        }
    }

    cout << ans << endl << sol.size() << endl;
    for (auto x : sol) cout << x.first << " " << x.second << '\n';


    return 0;
}