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

using namespace std;

const int MAX = 202202;

int N, M, Ans;
int Dad[MAX], Cnt[MAX];

vector< pair< int, pair<int, int> > > Edges;
vector< pair<int, int> > AnsVector;

#define f first
#define s second

void citire() {
    ifstream in("apm.in");
    in >> N >> M;
    for(int i = 1, A, B, C; i <= M; i++) {
        in >> A >> B >> C;
        Edges.push_back( make_pair(C, make_pair(A, B)));
    } in.close();
}

int Find(int X) {
    int R = X, Aux;
    while(X != Dad[X]) 
        X = Dad[X];
    while(R != X) {
        Aux = Dad[R];
        Dad[R] = X;
        R = Aux;
    } return X;
}

void Merge(int A, int B) {
    if(Cnt[A] > Cnt[B]) {
        Dad[B] = A;
        Cnt[A]++;
    } else {
        Dad[A] = B;
        Cnt[B]++;
    }
}

void solve() {
    for(int i = 1; i <= N; i++) {
        Dad[i] = i;
        Cnt[i] = 1;
    }
    sort(Edges.begin(), Edges.end());
    for(size_t i = 0; i < Edges.size(); i++) {
        if(Find(Edges[i].s.f) != Find(Edges[i].s.s)) {
            Ans += Edges[i].f;
            AnsVector.push_back(Edges[i].s);
            Merge(Find(Edges[i].s.f), Find(Edges[i].s.s));
        } 
    }
}

void afisare() {
    ofstream out("apm.out");
    out << Ans << "\n";
    out << AnsVector.size() << "\n";
    for(size_t i = 0; i < AnsVector.size(); i++) {
        out << AnsVector[i].f << " " << AnsVector[i].s << "\n";
    }
    out.close();
}

int main() {
    citire();
    solve();
    afisare();
}