#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

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

class muchie {
public:
    int a, b, c;
    inline bool operator<(const muchie& M) {
        return (c < M.c);
    }
    friend istream& operator>>(istream& is, muchie& M);
    friend ostream& operator<<(ostream& os, muchie& M);
};

istream& operator>>(istream& is, muchie& M) {
        is >> M.a >> M.b >> M.c;
        return is;
}

inline ostream& operator<<(ostream& os, muchie& M) {
        os << M.a << " " << M.b;
        return os;
}

vector<muchie> v(400001);
vector<int> grup(200001), rang(200001);

int find_set(int nod) {
    if (grup[nod] == nod)
        return nod;
    return (grup[nod] = find_set(grup[nod]));
}

void union_set(int a, int b) {
    if (rang[a] < rang[b])
        grup[a] = b;
    else
        grup[b] = a;
    if (rang[a] == rang[b])
        rang[a]++;
}

int main() {
    int n, m;
    muchie A;
    in >> n >> m;
    for (int i = 0; i < m; i++) {
        in >> A;
        v[i] = A; 
    }

    sort(v.begin(), v.end());
    vector<muchie> sol(n - 1);
    for (int i = 1; i <= n; i++) {
        grup[i] = i;
        rang[i] = 0;
    }

    int ra, rb, suma = 0, ind = 0;
    for (auto muchie : v) {
        ra = find_set(muchie.a);
        rb = find_set(muchie.b);
        if (ra != rb) {
            union_set(ra, rb);
            sol[ind++] = muchie;
            suma += muchie.c;
        }
    }

    out << suma << endl << sol.size() << endl;
    for (auto muchie: sol) {
        out << muchie << endl;
    }
    return 0;
}