#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vll vector<ll>
struct Dsu {
vll p, sz;
Dsu(ll n) : p(n), sz(n, 1) {
iota(p.begin(), p.end(), 0);
}
ll find(ll v) {
if (p[v] == v)
return v;
return p[v] = find(p[v]);
}
bool uni(ll a, ll b) {
ll x = find(a), y = find(b);
if (x == y)
return 0;
if (sz[x] < sz[y])
swap(x, y);
sz[x] += sz[y];
p[y] = x;
return 1;
}
};
struct Res {
ll T, C;
vector<pair<ll, ll>> e;
};
int main() {
ll n, m;
cin >> n >> m;
vector<tuple<ll, ll, ll, ll>> vec;
for (ll i = 0; i < m; ++i) {
ll a, b, c, d;
cin >> a >> b >> c >> d;
vec.push_back({c, d, a, b});
}
auto run = [&](ll p, ll q) -> Res {
vector<ll> id(m);
iota(id.begin(), id.end(), 0);
sort(id.begin(), id.end(), [&](ll i, ll j) {
auto [ti, ci, ai, bi] = vec[i];
auto [tj, cj, aj, bj] = vec[j];
ll wi = ti * q + ci * p;
ll wj = tj * q + cj * p;
if (wi != wj)
return wi < wj;
if (ti != tj)
return ti < tj;
if (ci != cj)
return ci < cj;
if (ai != aj)
return ai < aj;
return bi < bj;
});
Dsu dsu(n);
ll T = 0, C = 0, used = 0;
vector<pair<ll, ll>> e;
for (ll k = 0; k < id.size() && used < n - 1; ++k) {
auto [t, c, a, b] = vec[id[k]];
if (dsu.uni(a, b)) {
++used;
T += t;
C += c;
e.push_back({a, b});
}
}
return {T, C, e};
};
Res A = run(0, 1);
Res B = run(1, 0);
vector<Res> ans;
ans.push_back(A);
ans.push_back(B);
function<void(const Res&, const Res&)> hull = [&](const Res& X, const Res& Y) {
if (X.T == Y.T && X.C == Y.C)
return;
if (X.C == Y.C)
return;
ll p = (Y.T - X.T);
ll q = (X.C - Y.C);
Res Z = run(p, q);
if ((Z.T == X.T && Z.C == X.C) || (Z.T == Y.T && Z.C == Y.C))
return;
__int128 dx = ((__int128)Y.T - X.T);
__int128 dy = ((__int128)Y.C - X.C);
__int128 zx = ((__int128)Z.T - X.T);
__int128 zy = ((__int128)Z.C - X.C);
__int128 D = dx * zy - dy * zx;
if (D < 0) {
ans.push_back(Z);
hull(X, Z);
hull(Z, Y);
}
};
hull(A, B);
ll v = 4e18, cc = 0, tt = 0;
vector<pair<ll, ll>> pairs2;
for (auto& r : ans) {
if (r.e.size() == n - 1) {
ll val = r.T * r.C;
if (val < v) {
v = val;
cc = r.C;
tt = r.T;
pairs2 = r.e;
}
}
}
cout << tt << " " << cc << "\n";
for (auto [a, b] : pairs2)
cout << a << " " << b << "\n";
}
