#include <list>
#include <queue>
#include <vector>
#include <fstream>
#include <iostream>
#include <limits>
#include <numeric>

const int INF = INT32_MAX - 1;

struct Edge
{
    int from, to;
    int cost;
};

struct Node
{
    int id;
    Node *parent;
};


int main()
{
    std::ifstream fin("apm.in");
    int nNodes, nEdges;
    std::vector<std::vector<Edge>> edges;
    std::vector<Node> nodes;

    fin >> nNodes >> nEdges;
    edges.insert(edges.begin(), static_cast<unsigned long>(nNodes), {});
    nodes.insert(nodes.begin(), static_cast<unsigned long>(nNodes), {});

    for(auto &node: nodes)
    {
        static int id = 1;
        node.id = id++;
    }

    for(int i = 0; i < nEdges; i++)
    {
        Edge e{};
        fin >> e.from >> e.to >> e.cost;

        e.from --;
        e.to --;
        edges[e.from].push_back(e);
        edges[e.to].push_back({e.to, e.from, e.cost});
    }

    std::vector<int> distances;
    std::vector<bool> was, ok;
    std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<std::pair<int, int>>> pq;

    distances.insert(distances.begin(), static_cast<unsigned long>(nNodes), INF);
    was.insert(was.begin(), static_cast<unsigned long>(nNodes), false);
    ok.insert(ok.begin(), static_cast<unsigned long>(nNodes), false);

    distances[0] = 0;
    pq.push({distances[0], 0});
    while(!pq.empty())
    {
        while(!pq.empty() && was[pq.top().second] && ok[pq.top().second])
            pq.pop();

        if(!pq.empty())
        {
            int x = pq.top().second;
            pq.pop();
            was[x] = true;
            ok[x] = true;

            for(auto edge: edges[x])
            {
                if(!ok[edge.to] && edge.cost < distances[edge.to])
                {
                    distances[edge.to] = edge.cost;
                    nodes[edge.to].parent = &nodes[x];

                    pq.push({distances[edge.to], edge.to});
                }
            }
        }
    }

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

    fout << std::accumulate(distances.begin(), distances.end(), 0) << '\n';
    fout << nNodes - 1 << '\n';

    for(int i = 1; i < nNodes; i++)
        fout << nodes[i].id << ' ' << nodes[i].parent->id << '\n';

    return 0;
}