#include <bits/stdc++.h>
using namespace std;
const int N = 220;
const int M = 10020;
int n, m;
int par[N];
int sz[N];
int best_a, best_b;
int res = 2e9;
struct Point {
int x; int y;
Point(int x = 0, int y = 0): x(x), y(y) {}
};
struct Edge {
int u; int v; int x; int y;
} ed[M];
vector< pair<int,int> > vres;
int anc(int p) { return p == par[p] ? p : par[p] = anc(par[p]); }
void join(int p, int q) {
if (sz[p] < sz[q]) par[p] = q, sz[q] += sz[p], sz[p] = 0;
else par[q] = p, sz[p] += sz[q], sz[q] = 0;
}
Point getmst(int a, int b, bool trace = false) {
sort(ed, ed + m, [&](Edge p, Edge q) {
return a * p.x + b * p.y < a * q.x + b * q.y;
});
for (int i = 0; i < n; ++i) par[i] = i, sz[i] = 1;
int resx = 0;
int resy = 0;
int need = n - 1;
for (int i = 0; i < m; ++i) {
int u = anc(ed[i].u), v = anc(ed[i].v);
if (u == v) continue;
--need;
join(u, v);
resx += ed[i].x;
resy += ed[i].y;
if (trace) {
vres.push_back(make_pair(ed[i].u, ed[i].v));
}
if (!need) break;
}
if (res > 1LL * resx * resy) {
best_a = a;
best_b = b;
res = 1LL * resx * resy;
}
if (trace) {
printf("%d %d\n", resx, resy);
for (auto &e : vres) {
printf("%d %d\n", e.first, e.second);
}
}
return Point(resx, resy);
}
long long ccw(Point O, Point A, Point B) {
A.x -= O.x; A.y -= O.y;
B.x -= O.x; B.y -= O.y;
return 1LL * A.x * B.y - 1LL * A.y * B.x;
}
void solve(Point &p, Point &q) {
res = min(res, p.x * p.y);
res = min(res, q.x * q.y);
int b = q.x - p.x; // >= 0
int a = p.y - q.y; // >= 0
Point mid = getmst(a, b);
if (ccw(mid, q, p) <= 0) return;
solve(p, mid);
solve(mid, q);
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(0);
cin >> n >> m;
for (int i = 0; i < m; ++i) {
cin >> ed[i].u >> ed[i].v >> ed[i].x >> ed[i].y;
}
Point p = getmst(1, 0); // x
Point q = getmst(0, 1); // y
solve(p, q);
getmst(best_a, best_b, true);
}
