#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);

    priority_queue< pair<int,pair<int,int>>, vector<pair<int,pair<int,int>>>, greater<pair<int, pair<int,int>>>> Q;

    Q.push({0, {0, node}});
    int ans = 0;

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

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

        if(currentParent != 0)
            path.push_back({currentParent, currentNode});

        for(auto neighbor : graph[currentNode]) {
            int newNode = neighbor.second;
            int newWeight = neighbor.first;
            if(isVisited[newNode] == false) {
                Q.push({newWeight, {currentNode, newNode}});
            }
        }

    }
    return ans;

}

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;
}