#include <fstream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int n, m, x, y, z, total_muchii, k, xx, yy, zz, s;

vector<pair<int, int>> v[101], drum;
vector<pair<pair<int, int>, int>> muchii;
bool vizitat[101];

bool cmp(pair<pair<int, int>, int> a, pair<pair<int, int>, int> b) {
    return a.second < b.second;
}

bool cmp1(pair<int, int> a, pair<int, int> b) {
    return a.first < b.first;
}

void dfs(int m) {
    vizitat[m] = 1;
    for (auto u : v[m]) {
        if (!vizitat[u.first]) {
            if(!(m==xx && u.first==yy)){
                dfs(u.first);
            }
        }
    }
}

void dfs1(int m) {
    vizitat[m] = 1;
    for (auto u : v[m]) {
        if (!vizitat[u.first]) {
            drum.push_back({m, u.first});
            dfs1(u.first);
        }
    }
}


int main() {
    fin >> n >> m;
    total_muchii = m;
    for (int i = 1; i <= m; i++) {
        fin >> x >> y >> z;
        v[x].push_back({y, z});
        v[y].push_back({x, z});
        muchii.push_back({{x, y}, z});
        s += z;
    }
    sort(muchii.begin(), muchii.end(), cmp);

    for (int i = 1; i <= n; i++) {
        sort(v[i].begin(), v[i].end(), cmp1);
    }

    for (int i = m - 1; i >= 0; i--) {
        if (total_muchii > n - 1) {
            xx = muchii[i].first.first;
            yy = muchii[i].first.second;
            zz = muchii[i].second;

            bool ok = 0;
            dfs(xx);
            for (int i = 1; i <= n; i++) {
                if (vizitat[i] == 0) {
                    ok = 1;
                    break;
                }
            }
            memset(vizitat, 0, sizeof(vizitat));
            if (ok == 0) {
                for (auto it = v[xx].begin(); it != v[xx].end(); ++it) {
                    if (it->first == yy) {
                        v[xx].erase(it);
                        break;
                    }
                }

                for (auto it = v[yy].begin(); it != v[yy].end(); ++it) {
                    if (it->first == xx) {
                        v[yy].erase(it);
                        break;
                    }
                }

                s -= zz;
                total_muchii--;
            }
        }
    }

    memset(vizitat, 0, sizeof(vizitat));

    dfs1(1);

    fout << s << '\n';
    for (auto u : drum) {
        fout << u.first << " " << u.second << '\n';
    }
    return 0;
}