#include <fstream>
#include <vector>
#include <queue>

using namespace std;

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

vector<pair<int,int>> path;

int MST(int weight, int node, int noNodes, vector<vector<pair<int,int>>> &graph) {

    vector<bool> isVisited(noNodes+1, 0);
    vector<int> parent(noNodes+1, 0);
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> Q;

    Q.push({weight, node});

    int answer = 0;

    while(!Q.empty()) {
        int currentNode = Q.top().second;
        int currentWeight = Q.top().first;
        Q.pop();

        if(isVisited[currentNode] == true)
            continue;
        
        isVisited[currentNode] = true;
        answer += currentWeight;

        if(parent[currentNode] != 0)
            path.push_back({currentNode, parent[currentNode]});

        for(auto neighbor : graph[currentNode]) {
            if(!isVisited[neighbor.second])
                Q.push({neighbor.first, neighbor.second});
                parent[neighbor.second] = currentNode;
        }
    }
    return answer;

}

int main() {

    int noNodes, noEdges;
    vector<vector<pair<int,int>>> graph;
    fin >> noNodes >> noEdges;
    graph.resize(noNodes+1);

    while(noEdges--) {
        int firstNode, secondNode, weight;
        fin >> firstNode >> secondNode >> weight;
        graph[firstNode].push_back({weight,secondNode});
        graph[secondNode].push_back({weight,firstNode});
    }

    fout << MST(0, 1, noNodes, graph) << endl << noNodes-1 << endl;

    for(auto e : path)
        fout << e.first << ' ' << e.second << endl;


    return 0;
}