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

using namespace std;

struct arc
{
    int u, v;
    double w;

    bool operator<(const arc &a) const
    {
        return w < a.w;
    }
};

int findSet(int vertex, const vector<int> &parent)
{
    return (parent[vertex] == vertex) ? vertex : findSet(parent[vertex], parent);
}

void unionSets(int u, int v, vector<int> &parent)
{
    parent[findSet(v, parent)] = findSet(u, parent);
}

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

    int V, E;
    f >> V >> E;

    vector<arc> arcs(E);
    for (auto &a : arcs)
    {
        f >> a.u >> a.v >> a.w;
    }
    sort(arcs.begin(), arcs.end());

    vector<int> parent(V + 1);
    iota(parent.begin(), parent.end(), 0);

    int cost = 0;
    vector<arc> minimumSpanningTree;

    for (const auto &a : arcs)
    {
        if (findSet(a.u, parent) != findSet(a.v, parent))
        {
            cost += a.w;
            minimumSpanningTree.emplace_back(a);
            unionSets(a.u, a.v, parent);
        }
    }

    g << cost << '\n';
    g << minimumSpanningTree.size() << '\n';
    for (const auto &a : minimumSpanningTree)
    {
        g << a.u << ' ' << a.v << '\n';
    }

    return 0;
}