#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");

const int CAPACITY = 200013;

class DisjointForests
{
private:
    int n;
    int root[CAPACITY];

public:
    DisjointForests(int n)
    {
        this->n = n;
        for (int i = 1; i <= n; ++i)
        {
            root[i] = i;
        }
    }

    void join(int x, int y)
    {
        int rootX = getRoot(x);
        int rootY = getRoot(y);
        root[rootX] = rootY;
    }

    int getRoot(int x)
    {
        return x == root[x] ? x : root[x] = getRoot(root[x]);
    }
};

int n, m, a, b, c;
struct Link
{
    int from;
    int to;
    int cost;
};

int main()
{
    fin >> n >> m;
    Link links[m];
    DisjointForests forests(n);
    for (int i = 0; i < m; ++i)
    {
        fin >> a >> b >> c;
        links[i] = {a, b, c};
    }
    sort(links, links + m, [](const Link &a, const Link &b) -> bool
         { return a.cost < b.cost; });
    int sum = 0;
    vector<Link> ans;
    for (int i = 0; i < m; ++i)
    {
        Link l = links[i];
        if (forests.getRoot(l.from) != forests.getRoot(l.to))
        {
            sum += l.cost;
            forests.join(l.from, l.to);
            ans.push_back(l);
        }
    }
    fout << sum << "\n";
    fout << ans.size() << "\n";
    for (Link l : ans)
    {
        fout << l.from << " " << l.to << "\n";
    }
    return 0;
}