#include<vector>
#include<iostream>
#include<iomanip>
#include<chrono>
#include <random>
#include <cassert>
#include <queue>
#include <set>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long LL;
#define PB push_back
#define MP make_pair
#define A first
#define B second
#define SZ(x) int(x.size())
#define FR(i, a, b) for (int i = (a); i < (b); ++i)
#define FOR(i, n) FR(i, 0, n)
const int M = 1000000007;
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
#ifdef DEBUG
#define LOG(x) std::cout << x << std::endl
#else
#define LOG(X)
#endif
struct DSU {
vector<int> p, sz;
DSU(int n) {
p.clear(); sz.clear();
p.resize(n); sz.resize(n, 1);
iota(p.begin(), p.end(), 0);
}
int get(int x) {
if (x == p[x]) return x;
return p[x] = get(p[x]);
}
bool unite(int u, int v) {
u = get(u); v = get(v);
if (u == v) return false;
if (sz[u] < sz[v]) swap(u, v);
p[v] = u;
sz[u] += sz[v];
return true;
}
};
int n, m;
vector<vector<int>> e;
LL ans = 1LL << 60;
pair<int, int> ans_;
vector<pair<int, int>> e_;
pair<int, int> calc(vector<vector<int>>& edge) {
DSU T(n);
sort(edge.begin(), edge.end());
pair<int, int> cur{};
int cnt = 0;
vector<pair<int, int>> loc;
for (auto& i : edge) {
if (T.unite(i[1], i[2])) {
loc.PB(MP(i[1], i[2]));
cnt++;
cur.A += i[4];
cur.B += i[3];
}
}
assert(cnt == n - 1);
if ((LL)cur.A * cur.B < ans) {
ans = (LL)cur.A * cur.B;
ans_ = cur;
e_ = loc;
}
return cur;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
FOR(i, m) {
vector<int> tmp(4);
FOR(i, 4) cin >> tmp[i];
// tmp[0]--; tmp[1]--;
e.PB(tmp);
}
pair<int, int> a, b;
vector<vector<int>> tmp;
for (auto& i : e) {
tmp.PB({0, i[0], i[1], i[2], i[3]});
}
for (auto& i : tmp) i[0] = i[4];
a = calc(tmp);
for (auto& i : tmp) i[0] = i[3];
b = calc(tmp);
int d = 0;
auto find = [&](auto&& self, pair<int, int> l, pair<int, int> r) -> void {
d++;
assert(d <= 2000);
for (auto& i : tmp) {
i[0] = i[4] * (l.B - r.B) + i[3] * (r.A - l.A);
}
auto loc = calc(tmp);
LL cp = (LL)(r.A - l.A) * (loc.B - l.B) - (LL)(r.B - l.B) * (loc.A - l.A);
if (cp >= 0) return;
self(self, l, loc);
self(self, loc, r);
};
find(find, a, b);
cout << ans_.A << ' ' << ans_.B << '\n';
for (auto [u, v] : e_) {
cout << u << ' ' << v << '\n';
}
}
