#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;
using ll = long long;
using tiii = tuple<int, int, int, int>;
//using tii = tuple<int, int, int>;
using pii = pair<int, int>;
namespace DSU {
const int nmax = 2e5 + 5;
int dsu[nmax];
void init(int N) {
for(int i = 0; i <= N; i++) dsu[i] = i;
}
int f(int x) { return dsu[x] == x? x : dsu[x] = f(dsu[x]); }
void unite(int x, int y) {
dsu[f(x)] = f(y);
}
};
int N;
vector<tiii> edges;
vector<pii> cand;
pair<int, int> tangentLine(int a, int b) {
sort(all(edges), [&](auto x, auto y) { return get<2>(x) * a + get<3>(x) * b < get<2>(y) * a + get<3>(y) * b; });
cand.clear();
int X = 0, Y = 0;
DSU::init(N);
for(auto [u, v, x, y] : edges) {
if(DSU::f(u) == DSU::f(v));
else X += x, Y += y, cand.emplace_back(u, v), DSU::unite(u, v);
}
return pii{X, Y};
}
ll best = 2e10;
int a, b;
void upd(pii x, int ma, int mb) {
if(best > (ll)x.first * x.second) {
best = (ll)x.first * x.second;
a = ma;
b = mb;
}
}
void divide(pii l, pii r) {
int ma = -(l.second - r.second), mb = l.first - r.first;
//ma *= -1, mb *= -1;
//cerr << l.first << ' ' << l.second << '\n';
//cerr << r.first << ' ' << r.second << '\n';
auto x = tangentLine(ma, mb);
//cerr << x.first << ' ' << x.second << '\n';
if(x == l || x == r) return;
upd(x, ma, mb);
divide(l, x);
divide(x, r);
}
signed main() {
int m;
//...
cin >> N >> m;
edges.resize(m);
for(auto &[a, b, c, d] : edges)
cin >> a >> b >> c >> d;
divide(tangentLine(0, 1), tangentLine(1, 0));
upd(tangentLine(0, 1), 0, 1);
upd(tangentLine(1, 0), 1, 0);
auto [x, y] = tangentLine(a, b);
cout << x << ' ' << y << '\n';
for(auto [u, v] : cand) cout << u << ' ' << v << '\n';
}
