#include <iostream>
#include <utility>
#include <algorithm>
#include <vector>
#include <functional>
struct edge {
unsigned int a, b, t, c;
};
struct edge untitled_algorithm(
unsigned int N,
std::vector<edge> *const out,
std::vector<edge> *const graph,
const unsigned int t_weight,
const unsigned int c_weight
) {
out->clear();
out->reserve(N);
auto costof = [=] (edge e) {
return e.t * t_weight + e.c * c_weight;
};
std::sort(graph->begin(), graph->end(), [&] (edge a, edge b) {
return costof(a) < costof(b);
});
struct cant_be_anonymous { unsigned int up, rank; };
std::vector<cant_be_anonymous> dsu;
dsu.reserve(N);
for (unsigned int i = 0; i < N; ++i)
dsu.push_back({i, 0});
std::function<unsigned int(unsigned int)> repr;
repr = [&] (unsigned int i) {
if (dsu[i].up == i)
return i;
return dsu[i].up = repr(dsu[i].up);
};
auto merge = [&] (unsigned int i, unsigned int j) {
unsigned int k = dsu[i].rank < dsu[j].rank ? i : j;
dsu[k].up = i^j^k;
};
edge overall_motion = { 0, 0, 0, 0 };
for (const edge e : *graph) {
unsigned int a, b;
a = repr(e.a);
b = repr(e.b);
if (a != b) {
merge(a, b);
out->push_back({e.a, e.b, e.t, e.c});
overall_motion.t += e.t;
overall_motion.c += e.c;
}
}
return overall_motion;
}
int main(void) {
unsigned int N, M;
std::vector<edge> edges;
std::cin >> N >> M;
edges.reserve(M);
for (unsigned int i = 0; i < M; ++i) {
unsigned int a, b, t, c;
std::cin >> a >> b >> t >> c;
edges.push_back({a, b, t, c});
}
std::vector<edge> out;
edge overall_t = untitled_algorithm(N, &out, &edges, 1, 0);
edge overall_c = untitled_algorithm(N, &out, &edges, 0, 1);
int tw = overall_t.t - overall_c.t;
int cw = overall_c.c - overall_t.c;
edge overall = untitled_algorithm(N, &out, &edges, tw, cw);
std::cout << overall.t << " " << overall.c << "\n";
for (edge e : out) {
std::cout << e.a << " " << e.b << "\n";
}
}
