#include <fstream>
#include <algorithm>
#include <vector>
#include <tuple>
#define Nmax 200009
#define Emax 400009

using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");

typedef tuple <int, int, int> edge;

int n,m,x,y,c,root[Nmax],cost,usage;
vector <int> sol;
vector <edge> E;

bool compare(edge a, edge b) {

    return get<2>(a) < get<2>(b);
}

int getroot(int x) {

    if(root[x] != x) {

        root[x] = getroot(root[x]);
    }
    return root[x];
}


void reunion(int x, int y) {

    root[getroot(y)]=getroot(x);
}

bool check(int x, int y) {

    if (getroot(x)==getroot(y)) return 1;
    return 0;
}

void ReadInput() {

    f>>n>>m;

    for (int i=1; i<=m; ++i) {

        f>>x>>y>>c;
        E.push_back(edge(x,y,c));
    }
}

void Solve() {

    sort(E.begin(), E.end(), compare);

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

    int counter=0;
    for (auto &e: E) {

        int x=get<0>(e);
        int y=get<1>(e);
        int c=get<2>(e);

        if (!check(x , y)) {

            sol.push_back(counter);
            cost += c;
            ++usage;

            reunion(x , y);
        }

        ++counter;
    }
    g<<cost<<'\n'<<usage<<'\n';

    for (auto &x: sol) g<< get<0>(E[x]) <<' '<< get<1>(E[x]) <<'\n';

}

int main() {

    ReadInput();
    Solve();

    f.close(); g.close();
    return 0;
}