#include <vector>
#include <deque>
#include <fstream>
#include <unordered_map>
#include <iostream>
#include <tuple>
#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;

    public:
        void read();
        void reuneste(int a, int b, vector<int> &r) ;
        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);

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

    }

}



void Graph::reuneste(int a, int b, vector<int> &r) {
    int r1 = r[a];
    int r2 = r[b];
    for( int k = 1; k <= N ; k++) {
        if (r[k] == r2) {
            r[k] = r1;
        }
    }
}


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

    vector<int> reprezentant(N+1,0);
    int cost_min = 0;
    int edges_added = 0;
    int x, y;

    for(int i = 1; i<=N; i++) {
        reprezentant[i] = i;
    }
    for(int i = 0; i < M ; i++) {
        x = list_edges[i][1];
        y = list_edges[i][2];
        if (reprezentant[x] != reprezentant[y]) {
            apm.push_back({x,y});
            reuneste(x,y,reprezentant);
            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_bad();
    my_graph.apm_kruskal_good();




    return 0;



}