#include<bits/stdc++.h>
using namespace std;
#define int int64_t
#define pb push_back
#define pii pair<int, int>
#define st first
#define nd second
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
ostream& operator<<(ostream& os, pii x) {
os << "{" << x.st << ", " << x.nd << "}";
return os;
}
int n, m;
vector<pair<pii, pii>> edges;
int p[209];
int Find(int x) {
return x==p[x]?x:p[x]=Find(p[x]);
}
void Union(int a, int b) {
p[Find(a)] = Find(b);
}
pii ans;
vector<pii> res;
void mst(int a, int b) {
iota(p, p+n, 0);
res.clear();
ans = {0, 0};
vector<pair<int, pair<pii, pii>>> v;
for(auto [x, y]:edges) {
v.pb({a*y.st+b*y.nd, {x, y}});
}
sort(all(v));
for(auto [x, y]:v) {
if(Find(y.st.st)!=Find(y.st.nd)) {
res.pb(y.st);
ans.st+=y.nd.st;
ans.nd+=y.nd.nd;
Union(y.st.st, y.st.nd);
}
}
}
pii f(pii a, pii b) {
int x = b.st-a.st;
int y = b.nd-a.nd;
mst(-y, x);
int x1 = ans.st-a.st;
int y1 = ans.nd-a.nd;
pii ret;
if(a.st*a.nd<b.st*b.nd) {
ret = a;
} else {
ret = b;
}
pii mid = ans;
if(x*y1-x1*y<0) {
pii r1 = f(a, mid);
pii r2 = f(mid, b);
if(r1.st*r1.nd<ret.st*ret.nd) ret = r1;
if(r2.st*r2.nd<ret.st*ret.nd) ret = r2;
}
return ret;
}
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> m;
for(int i=0;i<m;i++) {
int a, b, c, d;
cin >> a >> b >> c >> d;
edges.pb({{a, b}, {c, d}});
}
int CNST = 1000000;
mst(CNST, 1);
pii p1 = ans;
mst(1, CNST);
pii p2 = ans;
pii ret = f(p1, p2);
mst(ret.nd, ret.st);
cout << ans.st << " " << ans.nd << "\n";
for(pii x:res) cout << x.st << " " << x.nd << "\n";
}
