#include <vector>
#include <deque>
#include <fstream>
#include <iostream>
#include <algorithm>

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


class Graph {
    int N;
    int M;
    vector <vector<int>> list_edges;
    vector <vector<int>> list_adj;
    vector <int> r;
    vector <int> parent;

    public:
        void read();
        int reprez(int x);
        void reuneste(int a, int b) ;
        void apm_kruskal_good();
        void apm();
        static bool comp(const vector<int>& vec1, const vector<int>& vec2){
            return vec1[0] < vec2[0];
        }


};



void Graph:: read() {
    fileIn >> N >> M;
    list_edges.resize(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;

    }

}




int Graph::reprez(int x) {
    int reprezentant = x;
    while (parent[reprezentant] != 0) {
        reprezentant = parent[reprezentant];
    }

    int y;
    while(parent[x]!=0) {
        y = parent[x];
        parent[x] = reprezentant;
        x = y;
    }
    return reprezentant;
}



void Graph::reuneste(int a, int b) {
    int r1 = reprez(a);
    int r2 = reprez(b);

    if(r[r1] > r[r2]) {
        parent[r2] = r1;
    } else {
        parent[r1] = r2;
        if (r[r1] == r[r2] ) {
            r[r2]++;
        }
    }
}



void Graph:: apm_kruskal_good() {
    vector<vector<int>> apm;
    sort(list_edges.begin(), list_edges.end(),comp);

    r.resize(N+1, 1);
    parent.resize(N+1, 0);
    int cost_min = 0;
    int edges_added = 0;
    int x, y;


    for(int i = 0; i < M ; i++) {
        x = list_edges[i][1];
        y = list_edges[i][2];
        if (reprez(x) != reprez(y)) {
            apm.push_back({x,y});
            reuneste(x,y);
            edges_added++;
            cost_min += list_edges[i][0];
        }
        if(edges_added == N-1) break;
    }


    fileOut <<  cost_min <<"\n";
    fileOut << edges_added<<"\n";
    for(auto m: apm) {
        fileOut << m[0] << " "<< m[1]<<"\n";
    }


}

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




    return 0;



}