#include <stdio.h>
#include <string.h>
#define N 200
#define M 10000
unsigned int X = 12345;
int rand_() {
return (X *= 3) >> 1;
}
int n;
int ii[M], jj[M], xx[M], yy[M], hh[M], m;
int a1, b1;
int compare(int h1, int h2) {
long long z1 = (long long) a1 * xx[h1] + (long long) b1 * yy[h1];
long long z2 = (long long) a1 * xx[h2] + (long long) b1 * yy[h2];
if (z1 != z2)
return z1 < z2 ? -1 : 1;
return xx[h1] != xx[h2] ? xx[h1] - xx[h2] : yy[h2] - yy[h1];
}
void sort(int *hh, int l, int r) {
while (l < r) {
int i = l, j = l, k = r, h = hh[l + rand_() % (r - l)], tmp;
while (j < k) {
int c = compare(hh[j], h);
if (c == 0)
j++;
else if (c < 0) {
tmp = hh[i], hh[i] = hh[j], hh[j] = tmp;
i++, j++;
} else {
k--;
tmp = hh[j], hh[j] = hh[k], hh[k] = tmp;
}
}
sort(hh, l, i);
l = k;
}
}
int ds[N];
int find(int i) {
return ds[i] < 0 ? i : (ds[i] = find(ds[i]));
}
int join(int i, int j) {
i = find(i);
j = find(j);
if (i == j)
return 0;
if (ds[i] > ds[j])
ds[i] = j;
else {
if (ds[i] == ds[j])
ds[i]--;
ds[j] = i;
}
return 1;
}
void solve(int a, int b, int *x, int *y, int print) {
int h, h_;
a1 = a, b1 = b;
for (h = 0; h < m; h++)
hh[h] = h;
sort(hh, 0, m);
memset(ds, -1, n * sizeof *ds);
*x = *y = 0;
for (h = 0; h < m; h++) {
h_ = hh[h];
if (join(ii[h_], jj[h_])) {
if (print)
printf("%d %d\n", ii[h_], jj[h_]);
*x += xx[h_], *y += yy[h_];
}
}
}
long long z_; int x_, y_, a_, b_;
void enumerate(int x1, int y1, int x2, int y2) {
int x, y;
long long z;
solve(y1 - y2, x2 - x1, &x, &y, 0);
if (x != x1 || y != y1)
enumerate(x1, y1, x, y), enumerate(x, y, x2, y2);
else {
z = (long long) x1 * y1;
if (z_ > z)
z_ = z, x_ = x1, y_ = y1, a_ = y1 - y2, b_ = x2 - x1;
}
}
int main() {
int h, x1, y1, x2, y2;
scanf("%d%d", &n, &m);
for (h = 0; h < m; h++)
scanf("%d%d%d%d", &ii[h], &jj[h], &xx[h], &yy[h]);
solve(1, 0, &x1, &y1, 0);
solve(0, 1, &x2, &y2, 0);
z_ = (long long) x2 * y2, x_ = x2, y_ = y2, a_ = 0, b_ = 1;
enumerate(x1, y1, x2, y2);
printf("%d %d\n", x_, y_);
solve(a_, b_, &x_, &y_, 1);
return 0;
}
