#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e4+1;
int n, m;
#define ld long double
#define ptype ll
struct vec {
public:
ptype x, y;
ld length() const {
return sqrt(x * x + y * y);
}
ptype lengthsq() const {
return x * x + y * y;
}
vec() {}
vec(ptype x, ptype y) : x(x), y(y) {}
vec& operator+=(const vec& T) {
x += T.x;
y += T.y;
return *this;
}
vec& operator-=(const vec& T) {
x -= T.x;
y -= T.y;
return *this;
}
vec& operator*=(const ptype& T) {
x *= T;
y *= T;
return *this;
}
vec operator+(const vec& T) const {
return vec(*this) += T;
}
vec operator-(const vec& T) const {
return vec(*this) -= T;
}
vec operator*(const ptype& T) const {
return vec(*this) *= T;
}
// cross product
friend ll operator^(const vec& a, const vec& buld) {
return (a.x * buld.y) - (a.y * buld.x);
}
// dot product
friend ll operator&(const vec& a, const vec& buld) {
return (a.x * buld.x) + (a.y * buld.y);
}
friend bool operator==(const vec &a, const vec &b) {
return a.x == b.x && a.y == b.y;
}
// unit vector
friend vec operator~(vec a) {
const ll jcd = gcd(a.x, a.y);
a.x /= jcd;
a.y /= jcd;
return a;
}
// inverse sides
friend vec operator!(vec a) {
a.x *= -1;
a.y *= -1;
return a;
}
};
vec norm(const vec& a) {
return vec(a.y, -a.x);
}
struct edge {
int x, y, t, c;
} e[N];
int par[N], cnt[N];
int root(int x) {
return par[x] == x ? x : par[x] = root(par[x]);
}
bool merge(int u, int v) {
u = root(u), v = root(v);
if (u == v) return false;
if (cnt[v] > cnt[u]) swap(u, v);
par[v] = u;
cnt[u] += cnt[v];
return true;
}
void init() {
for (int i = 0; i < n; par[i] = i, cnt[i] = 1, i++);
}
vec mst(int time_factor, int money_factor)
{
init();
sort(e, e + m, [&](edge x, edge y) {
return time_factor * x.t + money_factor * x.c <
time_factor * y.t + money_factor * y.c;
});
ll curtime = 0, curmoney = 0;
for (auto ed : e) {
if (merge(ed.x, ed.y)) {
curtime += ed.t;
curmoney += ed.c;
}
}
return vec(curtime, curmoney);
}
ll sol = 1e18;
vec best = vec(0,0);
void rec(vec a, vec b)
{
vec dir = norm(b-a);
dir = vec(a.y-b.y, b.x-a.x);
vec res = mst(dir.x, dir.y);
if (sol > res.x * res.y) {
sol = res.x * res.y;
best = dir;
}
if ((a.x*(b.y-res.y)+b.x*(res.y-a.y)+res.x*(a.y-b.y)) != 0) {
rec(a, res);
rec(res, b);
}
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n >> m;
for (int i = 0; i < m; i++)
cin >> e[i].x >> e[i].y >> e[i].t >> e[i].c;
vec mst_t = mst(1, 0),
mst_m = mst(0, 1);
best = vec(1, 0);
sol = mst_t.x * mst_t.y;
if (sol > mst_m.x * mst_m.y) {
sol = mst_m.x * mst_m.y;
best = vec(0, 1);
}
rec(mst_t, mst_m);
best = mst(best.x, best.y);
init();
cout << best.x << ' ' << best.y << '\n';
for (auto ed : e)
if (merge(ed.x, ed.y))
cout << ed.x << ' ' << ed.y << '\n';
}
