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

using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

vector<pair<int,pair<int, int>>> edges;

int n, m , T[200005] , cost;


int get_root(int x) {
    int root = x;
    while (T[root] > 0) {
        root = T[root];
    }

    while (x != root) {
        int t = T[x];
        T[x] = root;
        x = t;
    }

    return root;
}

bool join(int x, int y){

    int root_x = get_root(x);
    int root_y = get_root(y);

    if(root_x == root_y)
        return false;

    if(T[root_x] <= T[root_y]){
        T[root_x] += T[root_y];
        T[root_y] = root_x;
    }
    else{
        T[root_y] += T[root_x];
        T[root_x] = root_y;
    }
}


int main(){


    fin >> n >> m;
    for(int i = 1; i <= m; i++){
        int x , y ,c;
        fin >> x >> y >> c;
        edges.push_back(make_pair(c , make_pair(x , y)));

    }

    sort(edges.begin() , edges.end());

    for(int i = 1; i <= n; i++){
        T[i] = -1;
    }

    int total = 0;
    vector <pair< int , int>> sol;
    for(int i = 0; i < edges.size(); i++){
         cost = edges[i].first;
         int x = edges[i].second.first;
         int y = edges[i].second.second;

        if(join(x , y)){
            total += cost;
            sol.push_back(make_pair(x , y));
        }
    }

    fout << total << "\n";
    fout << sol.size() << "\n";
    for(int i = 0; i < sol.size(); i++){
        fout << sol[i].first << " " << sol[i].second <<"\n";
    }
    return 0 ;

}