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

using namespace std;
ifstream fileIn("apm.in");
ofstream fileOut("apm.out");


class Graph {
    int N;
    int M;
    vector <vector<int>> list_edges;
    vector <vector<pair<int, int>>> list_adj;
    vector<bool> visited;

    int min_cost = 0;


    public:
        void read();
        bool bfs(int node, int parent, bool out = false);
        void apm_prim(int start);
        static bool comp(const vector<int>& vec1, const vector<int>& vec2){
            return vec1[0] < vec2[0];
        }
        void add_edges(int node, std::priority_queue<vector<int>> &pq);



};


void Graph:: read() {
    fileIn >> N >> M;
    //list_edges.resize(M);
    //cout << N << M;
    list_adj.resize(N + 1);

    int a, b, cost;
    for(int i=0; i<= M-1; i++) {
            fileIn >> a >> b>> cost;
            //list_edges[i]={cost, a, b};  //list_edges[i][0] = cost !!!!!; list_edges[i][1] = a; list_edges[i][2]= b;
            list_adj[a].push_back({b,cost});
            list_adj[b]. push_back({a, cost});
            //cout << a << b << cost;
    }

}



void Graph::add_edges(int node, std::priority_queue<vector<int>> &pq) {
    visited[node] = true;

    for(auto edge: list_adj[node]) {
        if(!visited[edge.first]) {
            pq.push({-edge.second, node, edge.first});
            //cout << "in pq added : " << edge.second <<  " "<< node<< " "<<edge.first << "\n";
        }
    }
}


void Graph:: apm_prim(int start = 1) {
     std::priority_queue<vector<int> > pq;
     int edges_added = 0;
     visited.resize(N+1, false);
     int curr_node = start;
     add_edges(curr_node, pq);
     while(!pq.empty() && edges_added != N-1) {
        vector<int>edge = pq.top();
        pq.pop();
        curr_node = edge[2];

        if(!visited[curr_node]) {
            //cout <<"added "<< -edge[0] << " " <<edge[1] <<" " << edge[2] <<"\n";

            list_edges.push_back({edge[1], edge[2]});
            edges_added ++;
            min_cost += -edge[0];
            add_edges(curr_node, pq);
        }

     }
     //cout << min_cost << "\n";
     fileOut << min_cost << "\n";
     fileOut << edges_added << "\n";
     for(auto edge: list_edges) {
        fileOut << edge[0]<< " " << edge[1] << "\n";

     }

}

int main()  {
    Graph my_graph;
    my_graph.read();
    my_graph.apm_prim();




    return 0;



}