#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 <queue>
#include <algorithm>
#include <vector>
#include <tuple>
int main()
{
    int n, m, s = 0; in >> n >> m; std::vector<std::tuple<int, int, int>> V; while (m--)
        {int a, b, c; in >> a >> b >> c; V.push_back(std::make_tuple(c, a, b));}
    std::sort(V.begin(), V.end()); std::fill(A, A + n, -1);
    std::vector<std::tuple<int, int>> S; for (auto m: V)
    {
        int a = R(std::get<1>(m)), b = R(std::get<2>(m));
        if (a != b)
        {
            if (A[a] < A[b]) std::swap(a, b); A[b] += A[a]; A[a] = b;
            s += std::get<0>(m); S.push_back(std::make_tuple(std::get<1>(m), std::get<2>(m)));
        }
    }
    out << s << '\n' << S.size() << '\n'; for (auto s: S) out << std::get<0>(s) << ' ' << std::get<1>(s) << '\n';
}