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

using namespace std;

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

int par[200001];

struct muchie{
    int x, y, cost;

    bool operator<(const muchie& b) const {
        return cost < b.cost;
    }
};

vector<muchie> muchii;
vector<muchie> rez;

int sef(int x){
    if(par[x] == x){
        return x;
    }
    else{
        return par[x] = sef(par[x]);
    }
}

void join(int x, int y){
    int parx = sef(x);
    int pary = sef(y);

    par[parx] = pary;
}

int main()
{
    int n, muc;
    cin >> n >> muc;
    for(int i = 1; i <= n; i++){
        par[i] = i;
    }

    for(int i = 1; i <= muc; i++){
        int x, y, c;
        cin >> x >> y >> c;
        muchii.push_back({x, y, c});
    }

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

    int s = 0;
    for(auto m : muchii){
        if(sef(m.x) != sef(m.y)){
            join(m.x, m.y);
            s += m.cost;
            rez.push_back(m);
        }
    }

    cout << s << "\n";
    cout << rez.size() << "\n";
    for(auto m : rez){
        cout << m.x << " " << m.y << "\n";
    }
    return 0;
}