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

using namespace std;

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

struct Edge
{
    int x, y, cost;

    bool operator<(const Edge &other) const
    {
        return cost < other.cost;
    }
};

int n, m;
vector<Edge> edges;
vector<Edge> apm;
int bestAPMCost;
vector<int> t, pseudoHeight;

void read()
{
    fin >> n >> m;
    t = vector<int>(n + 1, -1);
    pseudoHeight = vector<int>(n + 1, 0);

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

int getTreeRoot(int node)
{
    if (t[node] == -1)
    {
        return node;
    }

    int root = getTreeRoot(t[node]);
    t[node] = root;
    return root;
}

bool areFromSameTree(int x, int y)
{
    return getTreeRoot(x) == getTreeRoot(y);
}

void uniteTrees(int x, int y)
{
    int rootX = getTreeRoot(x);
    int rootY = getTreeRoot(y);

    if (pseudoHeight[rootX] < pseudoHeight[rootY])
    {
        t[rootX] = rootY;
    }
    else
    {
        t[rootY] = rootX;
        if (pseudoHeight[rootX] == pseudoHeight[rootY])
        {
            ++pseudoHeight[rootX];
        }
    }
}

void buildAPM()
{
    int numberOfEdges = 0;
    for (const Edge &edge : edges)
    {
        if (numberOfEdges == n - 1)
        {
            return;
        }

        int x = edge.x;
        int y = edge.y;
        int cost = edge.cost;

        if (!areFromSameTree(x, y))
        {
            uniteTrees(x, y);
            apm.push_back(edge);
            bestAPMCost += cost;
        }
    }
}

void print()
{
    fout << bestAPMCost << '\n';
    fout << apm.size() << '\n';

    for (const Edge &edge : apm)
    {
        fout << edge.x << ' ' << edge.y << '\n';
    }
}

int main()
{
    read();
    sort(edges.begin(), edges.end());
    buildAPM();
    print();
    return 0;
}