#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>


using namespace std;

// Prim

int father(int position){

    return (position - 1) >> 1;
}

int left_son(int position){
    
    return (position << 1) + 1;
}

int right_son(int position){

    return (position << 1) + 2;
}

void sift_up(int node, vector<int>& heap, vector<int>& positions, const vector<int>& distances){

    int current_pos = positions[node];
    while(current_pos > 0 && distances[heap[current_pos]] < distances[heap[father(current_pos)]]){
        swap(positions[heap[current_pos]], positions[heap[father(current_pos)]]);
        swap(heap[current_pos], heap[father(current_pos)]);
        current_pos = father(current_pos);
    }
}

void sift_down(int node, vector<int>& heap, vector<int>& positions, const vector<int>& distances){

    int current_pos = positions[node], better_son = -1;
    while(better_son){

        better_son = 0;
        if(left_son(current_pos) < heap.size() && distances[heap[current_pos]] > distances[heap[left_son(current_pos)]])
            better_son = left_son(current_pos);
        if(right_son(current_pos) < heap.size() && distances[heap[current_pos]] > distances[heap[right_son(current_pos)]] && distances[heap[right_son(current_pos)]] < distances[heap[left_son(current_pos)]])
            better_son = right_son(current_pos);
        
        if(better_son){
            swap(positions[heap[current_pos]], positions[heap[better_son]]);
            swap(heap[better_son], heap[current_pos]);
            current_pos = better_son;
        }
    }
}

 vector<int> Prim(int startnode, const vector<vector<pair<int, int>>>& graph, int& apm_cost){

     vector<int> heap, distances, positions, dad;
     vector<bool> in_apm;
     for(int i = 0; i < graph.size(); ++i){
         heap.push_back(i);
         positions.push_back(i);
         distances.push_back(INT32_MAX);
         in_apm.push_back(false);
         dad.push_back(-1);
     }
     distances[startnode] = 0;

     while(!heap.empty()){

         int current_node = heap[0];
         positions[heap[0]] = -1;
         heap[0] = heap[heap.size() - 1];
         positions[heap[0]] = 0;
         heap.pop_back();

         in_apm[current_node] = true;

         sift_down(heap[0], heap, positions, distances);

            for(auto adjacent : graph[current_node])
                if(distances[adjacent.first] > adjacent.second && !in_apm[adjacent.first]){
                    distances[adjacent.first] = adjacent.second;
                    dad[adjacent.first] = current_node;
                    sift_up(adjacent.first, heap, positions, distances);
                }
     }
    for(int i = 0; i < graph.size(); ++i)
        apm_cost += distances[i];
    return dad;
 }


int main()
{
    ifstream cin("apm.in");
    ofstream cout("apm.out");
         

    int N, M;
    cin >> N >> M;

    vector<vector<pair<int, int>>> graph(N);

   for(int x, y, c; M > 0; --M){
       cin >> x >> y >> c;
       --x; --y;
       graph[x].push_back(make_pair(y, c));
       graph[y].push_back(make_pair(x, c));
   }

    int apm_cost = 0;
    vector<int> dad = Prim(0, graph, apm_cost);

    cout << apm_cost << "\n";
    cout << N - 1 << "\n";
    for(int i = 0; i < N; ++i)
       if(dad[i] != -1)
            cout << i + 1 << " " << dad[i] + 1 << "\n";
    
  
    cin.close();
    cout.close();

    return 0;
}