#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <numeric>

using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

class union_find
{
public:
    int set_find(int n)
    {
        vector<int> xs;

        while(n != _parent[n])
        {
            xs.push_back(n);
            n = _parent[n];
        }

        for(const auto& x : xs)
        {
            _parent[x] = n;
        }

        return n;
    }

    void set_union(int a, int b)
    {
        a = set_find(a);
        b = set_find(b);

        if(a != b)
        {
            if(_size[a] < _size[b])
            {
                _parent[a] = b;
                _size[b] += _size[a];
            }
            else
            {
                _parent[b] = a;
                _size[a] += _size[b];
            }
        }
    }

    union_find(int n)
    {
        for(int i = 0; i <= n; i++)
        {
            _parent.push_back(i);
            _size.push_back(1);
        }
    }

private:
    vector<int> _parent;
    vector<int> _size;
};

struct edge
{
    int x, y, cost;

    edge(int _x = 0, int _y = 0, int _cost = 0) :
        x(_x), y(_y), cost(_cost) {}

    friend bool operator<(const edge& e1, const edge& e2)
    {
        return e1.cost < e2.cost;
    }
};

vector<edge> kruskal(vector<edge>& es, int n, int m)
{
    sort(es.begin(), es.end());

    union_find uf(n);

    vector<edge> result;

    for(const auto& e : es)
    {
        if(uf.set_find(e.x) != uf.set_find(e.y))
        {
            result.push_back(e);
            uf.set_union(e.x, e.y);
        }

        if(result.size() == n - 1)
        {
            break;
        }
    }

    return result;
}

int main()
{
    int n, m;

    fin >> n >> m;

    vector<edge> es;

    for(int i = 1; i <= m; i++)
    {
        int x, y, cost;
        fin >> x >> y >> cost;

        es.push_back(edge(x, y, cost));
    }

    vector<edge> result = kruskal(es, n, m);

    auto add_cost = [](int acc, edge e)
    {
        return acc + e.cost;
    };

    fout << accumulate(result.begin(), result.end(), 0, add_cost) << '\n' << n - 1 << '\n';

    for(const auto& e : result)
        fout << e.x << ' ' << e.y << '\n';
}