#include<bits/stdc++.h>

using namespace std;

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

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

int n , m  , T[105];


	
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;
    }
    
    return true;
}




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)));
        
    }
    for(int i = 1; i <= n; i++){
        T[i] = -1;
    }
    
    sort(edges.begin() , edges.end());
    vector<pair <int, int>> sol;
    
    int total = 0;
    for(unsigned int i = 0; i < edges.size(); i++){
        int 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;
    fout << "\n";
    fout << (int) sol.size() << "\n";
    for(unsigned int i = 0; i < sol.size(); i++){
        fout << sol[i].first << " " << sol[i].second << "\n";
    }
    return 0;
}