#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) ;
        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;
            //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;

    }

}

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);




}

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;



}