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

using namespace std;

struct Edge
{
    int x, y, cost;
};

bool comparator(const Edge& a, const Edge& b)
{
    return a.cost < b.cost;
}

struct DSU
{
    vector<int> h, p;

    DSU(int n)
    {
        h.resize(n + 1);
        p.resize(n + 1);
        for (int i = 1; i <= n; ++i)
        {
            h[i] = 1;
            p[i] = i;
        }
    }

    int find(int x)
    {
        int r = x;
        while(r != p[r])
            r = p[r];
        int y = x;
        while(y != r)
        {
            int t = p[y];
            p[y] = r;
            y = t;
        }
        return r;
    }

    void _union(int x, int y)
    {
        x = find(x);
        y = find(y);
        if (x != y)
        {
            if (h[x] < h[y])
            {
                p[x] = y;
            }
            else
            {
                if (h[y] < h[x])
                    p[y] = x;
                else
                {
                    p[y] = x;
                    ++h[x];
                }
            }
        }
    }
};

int main()
{
    ifstream f("apm.in");
    int n, m;
    f >> n >> m;
    DSU d(n);
    vector<Edge> v;
    for (int i = 1; i <= m; ++i)
    {
        int x, y, c;
        f >> x >> y >> c;
        v.push_back(Edge{ x, y, c });
    }
    f.close();
    sort(v.begin(), v.end(), comparator);
    int sum = 0;
    vector<Edge> sol;
    for (auto it : v)
    {
        if (d.find(it.x) != d.find(it.y))
        {
            d._union(it.x, it.y);
            sum += it.cost;
            sol.push_back(it);
        }
    }
    ofstream g("apm.out");
    g << sum << '\n';
    g << sol.size() << '\n';
    for (auto it : sol)
        g << it.x << ' ' << it.y << '\n';
    g.close();
    return 0;
}