#include <queue>
#include <vector>
#include <fstream>
#include <limits>
#include <numeric>
#include <utility>

const int INF = std::numeric_limits<int>::max() - 1;

struct Edge
{
    int cost;
    int to;
};

bool operator > (const Edge& lhs, const Edge& rhs); // detaliu de implementare - neimportant

using Graph = std::vector<std::vector<Edge>>;
using MinHeapOfEdges = std::priority_queue<Edge, std::vector<Edge>, std::greater<Edge>>;

struct MST // Minimum span tree = Arbore partial de cost minim
{
    std::vector<int> costs;
    std::vector<int> parents;
};

void init_graph(Graph& g, int nodeCount)
{
    g.resize(nodeCount);
}

void add_edge(Graph& g, int a, int b, int cost)
{
    g[a].push_back({cost, b});
    g[b].push_back({cost, a});
}

MST prim_algorithm(const Graph& graph)
{
    MST mst;
    std::vector<char> was;

    was.resize(graph.size()); // Alocare memorie pentru noduri in vectorul de vizitat, de costuri respectiv de parinti
    mst.costs.resize(graph.size(), INF); // costurile sunt initial infinit
    mst.parents.resize(graph.size());

    MinHeapOfEdges pq;

    mst.costs[0] = 0;
    pq.push({0, 0});
    while(!pq.empty())
    {
        while(!pq.empty() && was[pq.top().to])
            pq.pop();

        if(!pq.empty())
        {
            int currentNode = pq.top().to;
            pq.pop();

            was[currentNode] = true;

            for(const auto& edge: graph[currentNode])//parcurgere muchii vecine
                if(!was[edge.to] && edge.cost < mst.costs[edge.to])
                {
                    mst.costs[edge.to] = edge.cost;
                    mst.parents[edge.to] = currentNode;

                    pq.push(edge);
                }
        }
    }

    return mst;
}

int main()
{
    std::ifstream fin("apm.in");
    int nNodes, nEdges;
    Graph graph;

    fin >> nNodes >> nEdges;

    init_graph(graph, nNodes);

    for(int i = 0; i < nEdges; i++)
    {
        int a, b, cost;
        fin >> a >> b >> cost;

        add_edge(graph, a - 1, b - 1, cost);
    }

    MST mst = prim_algorithm(graph);

    std::ofstream fout("apm.out");

    fout << std::accumulate(mst.costs.begin(), mst.costs.end(), 0) << '\n'; // costul arborelui
    fout << nNodes - 1 << '\n';

    for(int i = 1; i < nNodes; i++)
        fout << i + 1 << ' ' << mst.parents[i] + 1 << '\n';

    return 0;
}

bool operator > (const Edge& lhs, const Edge& rhs)
{
    return std::make_pair(lhs.cost, lhs.to) > std::make_pair(rhs.cost, rhs.to);
}