#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];
    vector < int > List[NMAX];

private:
    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, List[i].push_back(i);

        return;
    }

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

        x = t[x], y = t[y];

        if(x == y)
            return false;

        if((int)List[y].size() > (int)List[x].size())
            my_swap(x, y);

        for(auto it : List[y])
            t[it] = x, List[x].push_back(it);

        List[y].clear();

        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;
}