#include <bits/stdc++.h>

using namespace std;

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

vector <pair<int, pair<int, int>>> v;
int padure[200005];
int height[200005];

int find_root(int x) {
    if (padure[x]!=x) {
        int root_x = find_root(padure[x]);
        padure[x]=root_x;
        return root_x;
    }
    return x;
}

void join(int x, int y) {
    int root_x = find_root(x);
    int root_y = find_root(y);
    if (height[root_x]<height[root_y]) swap(root_x, root_y);
    if (height[root_x]==height[root_y]) height[root_x]++;
    padure[root_y] = root_x;
}

vector <pair<int, int>> sol;

int main()
{
    fin.tie(0); fin.sync_with_stdio(false);
    int n, m, x, y, c; fin>>n>>m;
    for (int i=1; i<=m; i++) {
        fin>>x>>y>>c;
        v.push_back({c, {x, y}});
    }
    sort(v.begin(), v.end());
    for (int i=1; i<=n; i++) padure[i]=i;
    int sum = 0;
    for (pair<int, pair<int, int>> p : v) {
        c = p.first, x = p.second.first, y = p.second.second;
        cout<<x<<' '<<y<<' '<<find_root(x)<<' '<<find_root(y)<<endl;
        if (find_root(x)!=find_root(y)) {
            sol.push_back({x, y});
            sum+=c;
            join(x, y);
        }
    }
    fout<<sum<<'\n';
    fout<<sol.size()<<'\n';
    for (pair<int, int> p : sol) {
        fout<<p.first<<' '<<p.second<<'\n';
    }
    return 0;
}