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

using namespace std;

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

class disjoint_set
{
    private:
        int Size;

        int* parent;
        int* h;

    public:
        disjoint_set();
        disjoint_set(const int _SIZE);
        ~disjoint_set();

        int Find(const int x);
        void Union(const int x, const int y);
};

disjoint_set :: disjoint_set()
{
    Size = 0;

    parent = NULL;
    h = NULL;
}

disjoint_set :: disjoint_set(const int _SIZE)
{
    Size = _SIZE;

    parent = new int[_SIZE + 1];
    h = new int [_SIZE + 1];

    for (int i = 1; i <= _SIZE; i++)
    {
        parent[i] = i;
        h[i] = 0;
    }
}

disjoint_set :: ~disjoint_set()
{
    delete[] parent;
    delete[] h;
}

int disjoint_set :: Find(const int x)
{
    if (parent[x] == x)
        return x;

    parent[x] = Find(parent[x]);

    return parent[x];
}

void disjoint_set :: Union(const int x, const int y)
{
    int px = Find(x);
    int py = Find(y);

    if (px == py)
        return;

    if (h[px] < h[py])
        parent[px] = py;
    else if (h[px] > h[py])
        parent[py] = px;
    else
    {
        parent[py] = px;
        h[px]++;
    }
}

struct edge
{
    int node1;
    int node2;
    int cost;

    edge()
    {
        node1 = 0;
        node2 = 0;
        cost = 0;
    }

    edge(const int _NODE1, const int _NODE2, const int _COST)
    {
        node1 = _NODE1;
        node2 = _NODE2;
        cost = _COST;
    }
};

bool compareEdges(edge a, edge b)
{
    return a.cost < b.cost;
}

int n, m;

vector < edge > edges;

void read()
{
    f >> n >> m;

    for (int i = 1; i <= m; i++)
    {
        int x, y, c; f >> x >> y >> c;
        edges.push_back(edge(x, y, c));
    }
}

void kruskal()
{
    int cost = 0;

    vector < pair < int, int > > ans;

    disjoint_set ds(n);

    sort(edges.begin(), edges.end(), compareEdges);

    for (auto it : edges)
    {
        if (ds.Find(it.node1) != ds.Find(it.node2))
        {
            cost += it.cost;
            ds.Union(it.node1, it.node2);
            ans.push_back(make_pair(it.node1, it.node2));
        }

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

    g << cost << "\n";
    g << ans.size() << "\n";
    for (auto it : ans)
        g << it.first << " " << it.second << "\n";
}

int main()
{
    read();
    kruskal();
    return 0;
}