#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;
    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;
}
 
ostream& operator<<(ostream& os, muchie& M) {
        os << M.a << " " << M.b;
        return os;
}
 
vector<muchie> v;
vector<int> grup(200001);
 
int find_set(int nod) {
    if (grup[nod] == nod)
        return nod;
    return (grup[nod] = find_set(grup[nod]));
}
 
inline void union_set(int a, int b) {
    grup[a] = b;
}
 
int main() {
    int n, m;
    muchie A;
    in >> n >> m;
    for (int i = 0; i < m; i++) {
        in >> A;
        v.push_back(A); 
    }
 
    sort(v.begin(), v.end());
    vector<muchie> sol;
    for (int i = 1; i <= n; i++) {
        grup[i] = i;
    }
 
    int ra, rb, suma = 0;
    for (auto&& muchie : v) {
        ra = find_set(muchie.a);
        rb = find_set(muchie.b);
        if (ra != rb) {
            union_set(ra, rb);
            sol.push_back(muchie);
            suma += muchie.c;
        }
    }
 
 
    out << suma << '\n' << sol.size() << '\n';
    for (auto muchie: sol) {
        out << muchie << '\n';
    }
    return 0;
}