#include <fstream>

#include <vector>

#include <set>
#include <queue>

struct edge
{
    int start_node, end_node, cost;

    edge()
    {
    }

    edge(int _start_node, int _end_node, int _cost) : start_node(_start_node), end_node(_end_node), cost(_cost)
    {
    }

    bool operator < (const edge& other) const
    {
        return cost >= other.cost;
    }
};

int main()
{
    std::ifstream fin("apm.in");
    std::ofstream fout("apm.out");

    int nodes, edges;

    fin >> nodes >> edges;

    std::priority_queue < edge > pq, other_pq;

    int node_a, node_b, node_cost;

    while(fin >> node_a >> node_b >> node_cost)
    {
        pq.push(edge(node_a, node_b, node_cost));
    }

    std::set < int > used;
    std::set < int > unused;

    used.insert(1);

    int k;
    for(k = 2 ; k <= nodes ; ++k)
        unused.insert(k);

    edge current_edge;

    bool found;
    int cost = 0;
    std::vector < edge > solution;

    while(!unused.empty())
    {
        found = false;
        if(!pq.empty())
        {
            current_edge = pq.top();
            pq.pop();

            if(used.find(current_edge.start_node) != used.end() && unused.find(current_edge.end_node) != unused.end())
            {
                solution.push_back(current_edge);

                used.insert(current_edge.end_node);
                unused.erase(current_edge.end_node);

                cost += current_edge.cost;

                found = true;
            }
            if(used.find(current_edge.end_node) != used.end() && unused.find(current_edge.start_node) != unused.end())
            {
                solution.push_back(current_edge);

                used.insert(current_edge.start_node);
                unused.erase(current_edge.start_node);

                cost += current_edge.cost;

                found = true;
            }

            other_pq.push(current_edge);
        }

        while(!other_pq.empty() && found)
        {
            pq.push(other_pq.top());
            other_pq.pop();
        }
    }

    fout << cost << "\n" << solution.size() << "\n";

    for(int i = 0 ; i < solution.size() ; ++i)
        fout << solution[i].start_node << " " << solution[i].end_node << "\n";

    return 0;
}