#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

typedef pair < int, int > PII;
typedef pair < int, PII > PIII;

const int NMAX = 2e5 + 1;

int N, M;

vector < PIII > Edges;

class Sets
{
    int t[NMAX], Size[NMAX];

private:
    inline int Find (int Node)
    {
        if(Node == t[Node])
            return Node;

        return (t[Node] = Find(t[Node]));
    }

    static inline void my_swap (int &x, int &y)
    {
        x = (x ^ y), y = (x ^ y), x = (x ^ y);

        return;
    }

public:
    inline void Initialize (int N)
    {
        for(int i = 1; i <= N; ++i)
            t[i] = i, Size[i] = 1;

        return;
    }

    inline bool Unify (int x, int y)
    {
        if(x == y)
            return false;

        x = Find(x), y = Find(y);

        if(x == y)
            return false;

        if(Size[y] > Size[x])
            my_swap(x, y);

        t[y] = x, Size[x] += Size[y], Size[y] = 0;

        return true;
    }
} DSU;

static inline void Read ()
{
    f.tie(nullptr);

    f >> N >> M;

    for(int i = 1; i <= M; ++i)
    {
        int x = 0, y = 0, c = 0;
        f >> x >> y >> c;

        Edges.push_back({c, {x, y}});
    }

    return;
}

static inline void Kruskal ()
{
    sort(Edges.begin(), Edges.end());

    vector < PII > _temp;

    int Total = 0;

    DSU.Initialize(N);

    for(auto it : Edges)
        if(DSU.Unify(it.second.first, it.second.second))
            Total += it.first, _temp.push_back(it.second);

    g << Total << '\n' << (N - 1) << '\n';

    for(auto it : _temp)
        g << it.first << ' ' << it.second << '\n';

    return;
}

int main ()
{
    Read();

    Kruskal();

    return 0;
}