#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <utility>

using namespace std;

ifstream in("grafpond.in");
ofstream out("grafpond.out");


int r[100];
int n, m;

void reprezentati() {
    for (int i = 1; i <= n; i++) {
        cout << r[i] << " ";
    }
}

void afisare(vector<vector<int>> graf) {

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < 3; j++)
            cout << graf[i][j] << " ";
        cout << endl;
    }

}

bool compare(vector<int> j, vector<int> i) {
    return (i[2] > j[2]);
}

int Reprez(int u) {
    return r[u];
}

void Reuneste(int u, int v) {
    int r1 = Reprez(u);//r1=r[u]
    int r2 = Reprez(v);//r2=r[v]
    for (int k = 1; k <= n; k++)
        if (r[k] == r2)
            r[k] = r1;
}

int main() {

    in >> n >> m;
    int x, y, z;
    vector<vector<int>> graf;
    for (int i = 0; i < m; i++) {
        vector<int> muchie;
        in >> x >> y >> z;
        muchie.push_back(x);
        muchie.push_back(y);
        muchie.push_back(z);
        graf.push_back(muchie);
    }
    sort(graf.begin(), graf.end(), compare);

    for (int i = 1; i <= n; i++)
        r[i] = i;

    int cost = 0;
    int nrmsel = 0;

    vector<pair<int,int>> apm;

    for (int i = 0; i < m; i++) {
        if (Reprez(graf[i][0]) != Reprez(graf[i][1])) {
            Reuneste(graf[i][0], graf[i][1]);
            //cout << graf[i][0] << " " << graf[i][1] << endl;
            apm.emplace_back(graf[i][0], graf[i][1]);
            cost += graf[i][2];
            nrmsel++;
            if (nrmsel == n - 1)
                break;
        }
    }
    out << cost<<endl <<nrmsel <<endl;
    for (int i=0;i<nrmsel;i++){
        out<<apm[i].first<<" "<<apm[i].second<<endl;
    }
    return 0;
}