#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
#define all(v) begin(v), end(v)
const int N = 1e4 + 4;
int n, m, l[N], r[N], a[N], b[N], w[N];
int par[N], sz[N], took[N];
int find(int u) {
return par[u] == u ? u : par[u] = find(par[u]);
}
bool unite(int u, int v) {
u = find(u), v = find(v);
if(u != v) {
if(sz[u] > sz[v]) swap(u, v);
sz[v] += sz[u], par[u] = v;
return 1;
} return 0;
}
ii solve(int A, int B) {
for(int i = 0; i < m; ++i) {
w[i] = A*a[i] + B*b[i];
}
iota(par, par+n, 0);
fill(sz, sz+n, 1), fill(took, took+m, 0);
static vi order(m);
fill(all(order), 0), iota(all(order), 0);
sort(all(order), [](int x, int y){ return w[x] < w[y]; });
int Asum = 0, Bsum = 0;
for(int i : order) {
if(unite(l[i], r[i])) {
Asum += a[i];
Bsum += b[i];
took[i] = 1;
}
} return {Asum, Bsum};
}
array<ll, 3> ans = {LLONG_MAX, 0, 0};
ii operator - (ii p, ii q) {
return {p.first - q.first, p.second - q.second};
}
ll cross(ii p, ii q) {
return (ll) p.first * q.second - (ll) p.second * q.first;
}
bool online(ii p, ii q, ii m) {
return cross(q-p, m-p) == 0;
}
void recur(ii p, ii q) {
if(p == q) return;
ii m = solve(q.second - p.second, p.first - q.first);
if(m == p or m == q or online(p, q, m)) return;
ans = min(ans, {(ll) m.first * m.second, q.second - p.second, p.first - q.first});
recur(p, m), recur(m, q);
}
int main(int argc, char const *argv[])
{
#ifdef LOCAL
freopen("in", "r", stdin);
#endif
scanf("%d %d", &n, &m);
for(int i = 0; i < m; ++i) {
scanf("%d %d %d %d", &l[i], &r[i], &a[i], &b[i]);
}
ii p = solve(0, 1), q = solve(1, 0);
ans = min(ans, {(ll) p.first * p.second, 0, 1});
ans = min(ans, {(ll) q.first * q.second, 1, 0});
recur(p, q);
auto [Asum, Bsum] = solve(ans[1], ans[2]);
printf("%d %d\n", Asum, Bsum);
for(int i = 0; i < m; ++i) {
if(took[i]) {
printf("%d %d\n", l[i], r[i]);
}
}
return 0;
}
