#include <bits/stdc++.h>
using namespace std;
typedef complex<long long> point;
const long long INF = (long long)1e18;
long long dot(point a, point b) {
return (conj(a) * b).real();
}
long long cross(point a, point b) {
return (conj(a) * b).imag();
}
long long area(point a, point b, point c) {
return cross(b - a, c - a);
}
struct DSU {
vector<int> f;
DSU(int n) : f(n) { iota(f.begin(), f.end(), 0); }
int leader(int x) {
while (x != f[x]) {
x = f[x] = f[f[x]];
}
return x;
}
bool unionize(int x, int y) {
x = leader(x);
y = leader(y);
if (x == y) {
return false;
}
f[y] = x;
return true;
}
};
int n, m;
vector<array<long long, 5>> edges0;
point f(point axis) { // find mst on axis
vector<array<long long, 5>> edges = edges0;
for (int i = 0; i < m; i++) {
edges[i][4] = dot(axis, point(edges[i][2], edges[i][3]));
}
sort(edges.begin(), edges.end(), [&](auto x, auto y) {
return x[4] < y[4];
});
point res(0, 0);
DSU dsu(n);
for (auto [u, v, a, b, w] : edges) {
if (dsu.unionize(u, v)) {
res += point(a, b);
}
}
return res;
}
int main() {
// ios::sync_with_stdio(false);
// cin.tie(nullptr);
cin >> n >> m;
edges0.resize(m);
for (int i = 0; i < m; i++) {
int u, v, a, b;
cin >> u >> v >> a >> b;
edges0[i] = {u, v, a, b, 0};
}
vector<point> S;
function<void(point, point)> divide = [&](point lp, point rp) {
point mid = (lp + rp);
point mp = f(mid);
// cout << lp << " " << rp << ":" << mp << '\n';
if (area(mp, lp, rp) >= 0) {
S.push_back(lp);
S.push_back(rp);
return;
}
divide(lp, mp);
divide(mp, rp);
};
divide(f(point(1, 0)), f(point(0, 1)));
long long mn = INF;
point key;
for (auto p : S) {
long long prod = p.real() * p.imag();
if (prod < mn) {
key = p;
mn = prod;
}
}
cout << key.real() << " " << key.imag() << "\n";
vector<array<long long, 5>> edges = edges0;
for (int i = 0; i < m; i++) {
edges[i][4] = dot(key, point(edges[i][2], edges[i][3]));
}
sort(edges.begin(), edges.end(), [&](auto x, auto y) {
return x[4] < y[4];
});
DSU dsu(n);
for (auto [u, v, a, b, w] : edges) {
if (dsu.unionize(u, v)) {
cout << u << " " << v << "\n";
}
}
}
