#include <bits/stdc++.h>
using namespace std;
struct pt{
long long int x, y;
pt operator + (const pt & p) const {
return pt{x + p.x, y + p.y};
}
pt operator - (const pt & p) const {
return pt{x - p.x, y - p.y};
}
__int128 cross(const pt & p) const {
return (__int128)x * p.y - (__int128)y * p.x;
}
};
struct EDGE {
long long int u, v, w, x, y;
};
vector<EDGE> e, ans;
int n, m, p[205], s[205];
long long int mi = 1e18, mix = 1e18, miy = 0;
bool cmp(EDGE aa, EDGE bb) {
return aa.w < bb.w;
}
int Find(int x) {
if (x == p[x]) return x;
return p[x] = Find(p[x]);
}
void Merge(int x, int y) {
x = Find(x);
y = Find(y);
if (x == y) return;
if (s[x] > s[y]) swap(x, y);
p[x] = y;
s[y] += s[x];
}
pt krusk(long long int x, long long int y) {
vector<EDGE> v = e, vv;
for (int i = 0; i < v.size(); i++) {
v[i].w = v[i].x * x + v[i].y * y;
}
for (int i = 1; i <= n; i++) p[i] = i, s[i] = 1;
sort(v.begin(), v.end(), cmp);
pt res = {0, 0};
for (auto w : v) {
if (Find(w.u) != Find(w.v)) {
Merge(w.u, w.v);
res.x += w.x;
res.y += w.y;
vv.push_back(w);
}
}
if (mi > res.x * res.y) {
mi = res.x * res.y;
mix = res.x; miy = res.y;
ans = vv;
}
else if (res.x * res.y == mi && res.x < mix) {
ans = vv;
mix = res.x; miy = res.y;
}
return res;
}
map<pair<long long int, long long int>, int> mm;
void trya(pt a, pt b) {
pt h = krusk(a.y - b.y, b.x - a.x);
if (mm.count({h.x, h.y})) return;
mm[{h.x, h.y}] = 1;
if ((b - a).cross(h - a) < 0) {
trya(a, h);
trya(h, b);
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> m;
for (int i = 1; i <= m; i++) {
int u, v, x, y;
cin >> u >> v >> x >> y;
e.push_back({u + 1, v + 1, 0, x, y});
}
pt a = krusk(1, 0), b = krusk(0, 1);
trya(a, b);
cout << mix << " " << miy << '\n';
for (auto w : ans) cout << w.u - 1 << " " << w.v - 1 << '\n';
}
