#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
struct DSU {
int n; vector<int> link, sz;
DSU(int n): n(n), link(n), sz(n, 1) {
iota(link.begin(), link.end(), 0);
}
int find(int x) {
return (x == link[x] ? x : link[x] = find(link[x]));
}
void unite(int x, int y) {
x = find(x), y = find(y);
if(sz[x] < sz[y]) {
swap(x, y);
}
sz[x] += sz[y], link[y] = x;
}
};
int main() {
ios_base::sync_with_stdio(false); cin.tie(0);
int n, m; cin >> n >> m;
vector<tuple<int, int, int, int>> edges;
vector<pair<int, int>> ratios;
for(int i = 0, x, y, t, c; i < m; i++) {
cin >> x >> y >> t >> c;
edges.emplace_back(x, y, t, c);
ratios.emplace_back(t, c);
}
tuple<ll, ll, ll> res = make_tuple(1e18, 1e18, 1e18);
vector<pair<int, int>> res_edges;
auto for_ratio = [&](ll a, ll b) {
sort(edges.begin(), edges.end(), [&](tuple<int, int, int, int> one, tuple<int, int, int, int> two) {
auto [x1, y1, t1, c1] = one;
auto [x2, y2, t2, c2] = two;
return a * t1 + b * c1 < a * t2 + b * c2;
});
DSU d(n); ll one = 0, two = 0;
vector<pair<int, int>> edges_here;
for(auto [x, y, t, c]: edges) {
if(d.find(x) == d.find(y)) continue;
d.unite(x, y);
edges_here.emplace_back(x, y);
one += t, two += c;
}
if(make_tuple(one * two, one, two) < res) {
res = make_tuple(one * two, one, two);
res_edges = edges_here;
}
return make_pair(one, two);
};
for_ratio(1, 0);
for_ratio(0, 1);
auto solve = [&](auto rec, pair<ll, ll> lo, pair<ll, ll> hi) -> void {
if(lo == hi) return;
pair<ll, ll> med = make_pair(lo.first + hi.first, lo.second + hi.second);
auto res = for_ratio(med.first, med.second);
swap(res.first, res.second);
if(res == lo || res == hi) return;
rec(rec, lo, res);
rec(rec, res, hi);
};
solve(solve, make_pair(1, 0), make_pair(0, 1));
auto [_, one, two] = res;
cout << one << " " << two << '\n';
for(auto [u, v]: res_edges) {
cout << u << " " << v << '\n';
}
}
