#include <fstream>
#define mF "apm"
std::ifstream in(mF ".in");
std::ofstream out(mF ".out");
int A[200001]; int R(int e) {if (0 < A[e]) return A[e] = R(A[e]); return e;}
#include <utility>
#define x first
#define y second
#include <algorithm>
#include <list>
int main()
{
    int n, m, s = 0; in >> n >> m; std::list<std::pair<int, std::pair<int, int>>> V; while (m--)
        V.emplace_back(), in >> V.back().y.x >> V.back().y.y >> V.back().x;
    V.sort(); std::fill(A, A + n, -1);
    for (auto i = V.begin(); i != V.end();)
    {
        int a = R(i->y.x), b = R(i->y.y); if (a == b) i = V.erase(i);
        else {s += i++->x; if (A[a] < A[b]) std::swap(a, b); A[b] += A[a]; A[a] = b;}
    }
    out << s << '\n' << V.size() << '\n'; for (auto p: V) out << p.y.x << ' ' << p.y.y << '\n';
}