#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) ;
        bool bfs(int node, int parent, bool out = false);
        void apm_kruskal_bad();
        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;

    }

}

bool Graph::bfs(int node, int parent, bool out) {
    if (parent == node) return false;
    vector<bool> visited(N+1, false);
    deque<int> q;
    visited[node] =  true;
    q.push_back(node);
    while(!q.empty()) {
        int n = q.front();
        q.pop_front();

        for(auto neib: list_adj[n]) {
            if (parent == neib) return false;
            if (!visited[neib])
            {
                visited[neib] = true;
                q.push_back(neib);
                if (out) fileOut << n << " " <<neib <<"\n";
            }
        }
    }
    return true;
}



void Graph:: apm_kruskal_bad() {
    //sort the edges by cost
    sort(list_edges.begin(), list_edges.end(),comp);
    int x, y;
    int cost_min = 0;
    int edges_added = 0;
    vector<bool> visited(N + 1, false);

    for(int i = 0; i < M ; i++) {

        x = list_edges[i][1];
        y = list_edges[i][2];
        cout << x <<" "<< y <<"cost" << list_edges[i][0] <<"\n";


        if(bfs(x, y)) {
            list_adj[x].push_back(y);
            list_adj[y].push_back(x);
            edges_added ++;
            cost_min += list_edges[i][0];
            cout << "MUCHIE ALEASA ->>> " << x << "," <<y << "cost " <<list_edges[i][0]<<"\n";
        }


        cout <<"muchii adaugate" << edges_added <<"\n";
        if(edges_added == N-1) {
            break;
        }

    }

    fileOut <<  cost_min <<"\n";
    fileOut << edges_added<<"\n";
    bfs(1,N+1, true);




}


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_bad();
    my_graph.apm_kruskal_good();




    return 0;



}