// Online C++ compiler to run C++ program online
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

int m,n;
vector<pair<int, pair<int, int>>> muchii;
vector<pair<int, int>> apcm;
vector<int> t;
vector<int> r;
int cost_total;

int Find(int nod) {
    while(t[nod] != 0){
        nod = t[nod];
    }
    return nod;
}

void _Union(int x, int y){
    int t_x = t[x];
    int t_y = t[y];
    
    if (r[t_x] > r[t_y]) {
        t[t_y] = t_x; 
    } else {
        t[t_x] = t_y;
        if (r[t_x] == r[t_y]) {
            r[t_y]++;
        }
    }
}

void Afisare(){
    cout << cost_total << endl;
    cout << apcm.size() << endl;
    for(auto m : apcm){
        cout << m.first << " " << m.second << endl;
    }
}

int main() {
    ifstream cin("apm.in");
    ofstream cout("apm.out");
    
    cin >> m >> n;
    t.assign(n + 1, 0);
    r.assign(n + 1, 0);
    
    for(int i; i < m; i++) {
        int a,b,c;
        cin >> a >> b >> c;
        muchii.push_back({c, {a, b}});
    }
    sort(muchii.begin(), muchii.end());
    
    for(auto muchie : muchii){
        
        int cost = muchie.first;
        int x = muchie.second.first;
        int y = muchie.second.second;
        
        if(Find(x) != Find(y)) {
            _Union(x, y);
            apcm.push_back({x,y});
            cost_total += cost;
            
            if(apcm.size() == n - 1)
                break;
        }
        
    }
    
    Afisare();
    
    return 0;
}