#include <bits/stdc++.h>

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

struct edge{
    int cost, node;
};

struct edgeTree{
    int cost, nodeA, nodeB;
    bool operator>(const edgeTree& other) const
    {
        return cost > other.cost;
    }
};

const int minim = -1001;

void prim(std::vector<std::vector<edge>>& graph, int vertices)
{
    int cost = 0;
    std::vector<edgeTree> apcmTree;

    std::priority_queue<edgeTree, std::vector<edgeTree>, std::greater<edgeTree>> pq;
    std::vector<char> visited(vertices + 1, false);

    pq.push({0, 1, 1}); // node 1 has an edge of cost 0 to node 1 

    while (!pq.empty())
    {
        edgeTree curr = pq.top();
        pq.pop();
        
        if (!visited[curr.nodeA])
        {
            cost += curr.cost;
            visited[curr.nodeA] = true;

            apcmTree.push_back(curr);
            
            for (edge e : graph[curr.nodeA])
                if (!visited[e.node])
                    pq.push({e.cost, e.node, curr.nodeA});
        }
    }

    fout<<cost<<'\n'<<apcmTree.size() - 1<< '\n';
    for (size_t index = 1; index < apcmTree.size(); index++)
        fout<<apcmTree[index].nodeA<<' '<<apcmTree[index].nodeB<<'\n';

}


int main()
{
    int numEdges, numNodes, a, b,c;

    fin>>numNodes>>numEdges;

    std::vector<std::vector<edge>> graph(numNodes + 1);
    for (int i = 0 ; i < numEdges; i++)
    {
        fin>>a>>b>>c;
        graph[a].push_back({c,b});
        graph[b].push_back({c,a});
    }

    prim(graph, numNodes);
    
    return 0;
}