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

using namespace std;

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

#define cin in 
#define cout out 

struct Edge {
    int x, y, cost;
    bool operator < (const Edge& him) {
        return cost < him.cost;
    }
};

class DSU {
    int n;
    vector<int> par, size;
public:
    DSU(int _n) : n(_n) {
        par.resize(n + 1);
        for (int i = 1; i <= n; ++i) {
            par[i] = i;
        }
        size.assign(n + 1, 1);
    }
    int getRoot(int x) {
        return x == par[x] ? x : par[x] = getRoot(par[x]);
    }

    bool unite(int x, int y) {
        x = getRoot(x);
        y = getRoot(y);
        if (x == y) {
            return false;
        }
        if (size[x] >= size[y]) {
            swap(x, y);
        }
        par[x] = y;
        size[y] += size[x];
        return true;
    }
};

vector<Edge> edges, answer;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int N, M;
    cin >> N >> M;

    for (int i = 1; i <= M; ++i) {
        int x, y, cost;
        cin >> x >> y >> cost;
        edges.push_back({ x, y, cost });
    }

    sort(edges.begin(), edges.end());
    DSU dsu(N);

    long long totalCost = 0;
    for (auto e: edges) {
        if (dsu.unite(e.x, e.y)) {
            answer.push_back(e);
            totalCost += e.cost;
        }
    }
    
    cout << totalCost << '\n';
    cout << answer.size() << '\n';
    for (auto it : answer) {
        cout << it.x << ' ' << it.y << '\n';
    }

    return 0;
}