#include <fstream>
#include <vector>
#include <queue>

using namespace std;

class DisjointSet
{
    public:
        DisjointSet(int size);
        void unionSets(int x, int y);
        int findParent(int x);

    private:
        vector<int> parent, rank;
        void link(int x, int y);

};

DisjointSet::DisjointSet(int size)
{
    parent.resize(size);
    for (int i = 0; i < size; i++)
        parent[i] = i;
    rank.resize(size, 1);
}

int DisjointSet::findParent(int x)
{
    int i = x;
    for (; parent[i] != i; i = parent[i]);

    while (x != parent[x])
    {
        int up = parent[x];
        parent[x] = i;
        x = up;
    }

    return i;
}

void DisjointSet::link(int x, int y)
{
    if (rank[x] < rank[y])
        parent[x] = y;
    else if (rank[x] > rank[y])
        parent[y] = x;
    else
    {
        parent[x] = y;
        rank[y]++;
    }
}

void DisjointSet::unionSets(int x, int y)
{
    link(findParent(x), findParent(y));
}

//typedef pair<int, int> tuple;
//typedef pair<tuple, int> triple;

struct comparator
{
 bool operator()(pair< pair<int, int>, int > x, pair< pair<int, int>, int > y)
 {
    return x.second > y.second;
 }
};

int main()
{
    ifstream in("apm.in");
    ofstream out("apm.out");

    int n, m;
    in >> n >> m;

    if (n < 1 || n > 200000 || m < 1 || m > 400000)
        return 1;

    priority_queue<int, vector<pair< pair<int, int>, int > >, comparator> heap;

    for (int i = 0; i < m; i++)
    {
        int x, y, c;
        in >> x >> y >> c;
        x--;
        y--;
        heap.push(pair< pair<int, int>, int >(pair<int, int>(x, y), c));
    }

    int apmCost = 0;
    vector< pair<int, int> > apmEdges;

    DisjointSet apm(n);

    while (apmEdges.size() != n - 1)
    {
        pair< pair<int, int>, int > edge = heap.top();
        heap.pop();

        if (apm.findParent(edge.first.first) != apm.findParent(edge.first.second))
        {
            apm.unionSets(edge.first.first, edge.first.second);
            apmEdges.push_back(edge.first);
            apmCost += edge.second;
        }
    }

    out << apmCost << "\n" << apmEdges.size() << endl;
    for (int i = 0; i < apmEdges.size(); i++)
        out << apmEdges[i].first + 1 << " " << apmEdges[i].second + 1 << endl;

    return 0;
}