#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define sz(x) (int)size(x)
#define all(x) (x).begin(), (x).end()
struct Dsu{
vector<int> par;
Dsu(int n){
par.resize(n);
iota(all(par), 0);
}
int find(int u){
if(par[u] == u) return u;
return par[u] = find(par[u]);
}
void merg(int u, int v){
u = find(u), v = find(v);
if(u == v) return;
par[u] = v;
}
};
int main(){
cin.tie(0)->sync_with_stdio(false);
int n, m;
cin >> n >> m;
vector<tuple<int, int, int, int>> edges;
for(int i = 0; i < m; i++){
int u, v, x, y;
cin >> u >> v >> x >> y;
edges.emplace_back(u, v, x, y);
}
auto calc = [&](ll a, ll b) -> tuple<ll, ll, vector<pair<int, int>>> {
sort(all(edges), [&](auto e, auto f){
auto [u1, v1, x1, y1] = e;
auto [u2, v2, x2, y2] = f;
ll z1 = a*x1+b*y1;
ll z2 = a*x2+b*y2;
if(z1 != z2) return z1 < z2;
return x1 < x2;
});
Dsu dsu(n);
ll resX = 0, resY = 0;
vector<pair<int, int>> res;
for(auto [u, v, x, y] : edges){
if(dsu.find(u) != dsu.find(v)){
dsu.merg(u, v);
resX += x;
resY += y;
res.emplace_back(u, v);
}
}
return {resX, resY, res};
};
ll ansX = 1e9, ansY = 1e9;
vector<pair<int, int>> ansEdges;
auto rec = [&](auto&& self, ll x1, ll y1, ll x2, ll y2) -> void {
assert(x1 <= x2);
if(x1 == x2){
assert(y1 == y2);
return;
}
auto [x, y, e] = calc(y1-y2, x2-x1);
if(x*y < ansX*ansY) ansX = x, ansY = y, ansEdges = e;
assert(x < x2);
if(x == x1) return;
self(self, x1, y1, x, y);
self(self, x, y, x2, y2);
};
auto [x1, y1, e1] = calc(1, 0);
auto [x2, y2, e2] = calc(0, 1);
if(x1*y1 < ansX*ansY) ansX = x1, ansY = y1, ansEdges = e1;
if(x2*y2 < ansX*ansY) ansX = x2, ansY = y2, ansEdges = e2;
rec(rec, x1, y1, x2, y2);
cout << ansX << " " << ansY << "\n";
for(auto [u, v] : ansEdges){
cout << u << " " << v << "\n";
}
}
