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

using namespace std;

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

int sefi[200001];
vector<pair<int, pair<int, int>>> muchii;
int muchii_luate[200001];

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

void join(int x, int y){
    int sx = sef(x);
    int sy = sef(y);
    sefi[x] = sy;
}

int main()
{
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        sefi[i] = i;
    }
    for(int i = 1; i <= m; i++){
        int x, y, c;
        cin >> x >> y >> c;
        muchii.push_back(make_pair(c, make_pair(x, y)));
    }
    sort(muchii.begin(), muchii.end());
    int luate = 0;
    int i = 0;
    int cost = 0;
    while(luate < n-1 && i <= m){
        if(sef(muchii[i].second.first) != sef(muchii[i].second.second)){
            luate++;
            muchii_luate[i] = 1;
            cost += muchii[i].first;
            join(muchii[i].second.first, muchii[i].second.second);
        }
        i++;
    }
    cout << cost << "\n";
    cout << luate << "\n";
    for(int i = 0; i <= 200000; i++){
        if(muchii_luate[i] != 0){
            cout << muchii[i].second.first << " " << muchii[i].second.second << "\n";
        }
    }
    return 0;
}