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

using namespace std;
const int MMAX = 400000;

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

struct muchii{
    int a, b, cost;
    bool operator <(const muchii & rhs) const {
        return cost < rhs.cost;
    }
}v[MMAX + 2];

int n;
struct DSU{
    vector <int> parent, sizes;
    void init() {
        parent.resize(n + 1);
        sizes.assign(n + 1, 1);
        for(int i = 1; i <= n; i++)
            parent[i] = i;
    }
    int findd(int u) {
        if(parent[u] == u)
            return u;
        return parent[u] = findd(parent[u]);
    }
    bool unite(int u, int w) {
        u = findd(u);
        w = findd(w);
        if(u == w)
            return false;
        if(sizes[w] > sizes[u])
            swap(u, w);
        parent[w] = u;
        sizes[u] += sizes[w];
        sizes[w] = 0;
        return true;
    }
}dsu;
vector <pair <int, int>> ans;
int main() {
    int m;
    cin >> n >> m;
    for(int i = 1; i <= m; i++)
        cin >> v[i].a >> v[i].b >> v[i].cost;
    sort(v + 1, v + m + 1);
    dsu.init();
    int sum = 0;
    for(int i = 1; i <= m; i++) {
        if(dsu.unite(v[i].a, v[i].b)) {
            sum += v[i].cost;
            ans.push_back({v[i].a, v[i].b});
        }
    }
    cout << sum << '\n';
    cout << ans.size() << '\n';
    for(const pair <int, int>& x : ans)
        cout << x.first << " " << x.second << '\n';
    return 0;
}