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




using namespace std;
int n, m;
vector<pair<int, pair<int, int>>> muchii;
vector<pair<int, int>> apcm;
vector<int> tt;
vector<int> r;

int cost_total;
ifstream cin("apm.in");
ofstream cout("apm.out");

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

void Union(int x, int y){
    int tt_x = Find(x);
    int tt_y = Find(y);

    if (r[tt_x] > r[tt_y]){
        tt[tt_y] = tt_x;
    }
    else {
        tt[tt_x] = tt_y;
        if (r[tt_x] == r[tt_y]){
            r[tt_y] ++;
        }
    }

}


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

}

int main(){
    cin>>n>>m;
    tt.assign(n+1, 0);
    r.assign(n+1, 0);
    for(int i=0; i<m; i++){
        int x, y, c;
        cin>>x>>y>>c;
        muchii.push_back({c, {x,y}});
    }
    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;
}