#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;
struct DSU {
vector<int> par;
void init(int n) { par.assign(n, -1); }
int rt(int v) { return par[v] == -1? v: (par[v] = rt(par[v])); }
bool unite(int v, int u) {
v = rt(v);
u = rt(u);
if (v == u)
return 0;
par[u] = v;
return 1;
}
};
struct P2 {
int x, y;
typedef const P2 &R;
P2 operator+(R q) const { return {x + q.x, y + q.y}; }
P2 operator*(int a) const { return {x*a, y*a}; }
P2 operator-(R q) const { return *this + q*-1; }
ll dot(R q) const { return (ll)x * q.x + (ll)y * q.y; }
ll cross(R q) const { return (ll)x * q.y - (ll)y * q.x; }
P2 normal() const { return {-y, x}; }
ll val() const { return (ll)x * y; }
bool operator<(R q) const { return val() < q.val(); }
};
vector<pair<pii,P2>> edges;
vector<pii> solve_edges;
int n;
P2 solve(P2 v)
{
vector<pair<ll,int>> e;
Loop (i,0,edges.size()) {
auto u = edges[i].second;
e.push_back({v.dot(u), i});
}
sort(e.begin(), e.end());
DSU dsu;
dsu.init(n);
solve_edges.clear();
int sx = 0, sy = 0;
for (auto [w, i] : e) {
auto [a, b] = edges[i].first;
auto [x, y] = edges[i].second;
if (dsu.unite(a, b)) {
sx += x;
sy += y;
solve_edges.emplace_back(a, b);
}
}
return {sx, sy};
}
ostream &operator<<(ostream &s, P2 p) {
return s << '(' << p.x << ',' << p.y << ')';
}
pair<P2,P2> dc(pair<P2,P2> pnl, pair<P2,P2> pnr)
{
auto pl = pnl.first;
auto pr = pnr.first;
//cerr << pl << ' ' << pr << '\n';
if (pl.x == pr.x && pl.y == pr.y)
return pnl;
P2 n = (pr - pl).normal();
P2 p = solve(n);
pair<P2,P2> pn = {p, n};
if ((pr - p).cross(pl - p) == 0)
return min(pnl, pnr);
return min(dc(pnl, pn), dc(pn, pnr));
}
int main()
{
cin.tie(0) -> sync_with_stdio(false);
int m;
cin >> n >> m;
Loop (i,0,m) {
int v, u, x, y;
cin >> v >> u >> x >> y;
edges.push_back({{v, u}, {x, y}});
}
P2 pl = solve({1,0});
P2 pr = solve({0,1});
auto [ans, nr] = dc({pl,{1,0}}, {pr,{0,1}});
cout << ans.x << ' ' << ans.y << '\n';
solve(nr);
for (auto [v, u] : solve_edges)
cout << v << ' ' << u << '\n';
}
