#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#define N 200005
#define f first
#define s second
using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");
vector<pair<int, pair<int, int> > > v;
vector<pair<int, int> > res;
long long cost;
int n, m, dsu[N];

void init_dsu() {
        for (int i = 1; i <= n; i++)
                dsu[i] = i;
}

int find_set(int x) {
        if (dsu[x] == x)
                return x;
        int y = find_set(dsu[x]);
        dsu[x] = y;
        return y;
}

void merge_sets(int x, int y) {
        x = find_set(x);
        y = find_set(y);
        dsu[x] = y;
}

int main() {
        in >> n >> m;
        init_dsu();

        int x, y, z;
        for (int i = 1; i <= m; i++) {
                in >> x >> y >> z;
                v.push_back(make_pair(z, make_pair(x, y)));
        }

        sort(v.begin(), v.end());

        for (int i = 0; i < m; i++) {
                x = find_set(v[i].s.f);
                y = find_set(v[i].s.s);
                if (x != y) {
                        merge_sets(x, y);
                        if (v[i].s.f > v[i].s.s)
                                swap(v[i].s.f, v[i].s.s);
                        res.push_back(make_pair(v[i].s.f, v[i].s.s));
                        cost += v[i].f;
                }
        }

        out << cost << "\n" << res.size() << "\n";

        for (int i = 0; i < res.size(); i++)
                out << res[i].f << " " << res[i].s << "\n";
        return 0;
}