#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
typedef long long ll;
using namespace __gnu_pbds;
using namespace std;
struct Edge {
ll a, b, t, m;
};
int n;
vector<Edge> edges;
vector<ll> rep, sz;
vector<Edge> res; // aktualne MST
ll Find(ll v) {
return (rep[v] == v ? v : rep[v] = Find(rep[v]));
}
bool Union(ll a, ll b) {
a = Find(a);
b = Find(b);
if (a == b) return false;
if (sz[b] > sz[a]) swap(a, b);
rep[b] = a;
sz[a] += sz[b];
return true;
}
// MST dla kombinacji wag: wsp1 * t + wsp2 * m
pair<ll, ll> mst(ll wsp1, ll wsp2) {
res.clear();
for (int i = 0; i < n; ++i) {
rep[i] = i;
sz[i] = 1;
}
ll czas = 0, money = 0;
sort(edges.begin(), edges.end(), [&](Edge x, Edge y) {
return wsp1 * x.t + wsp2 * x.m < wsp1 * y.t + wsp2 * y.m;
});
for (auto [a, b, t, m] : edges) {
if (Union(a, b)) {
czas += t;
money += m;
res.push_back({a, b, t, m});
}
}
return {czas, money};
}
// Rekurencyjny podział dla MST w dwóch wymiarach
pair<ll, pair<ll,ll>> rek(pair<ll,ll> l, pair<ll,ll> r) {
ll wa = r.second - l.second;
ll wb = -(r.first - l.first); // <- znak minus jest kluczowy
auto nowy = mst(wa, wb);
if ((nowy == l) || (nowy == r) || (wa * nowy.first + wb * nowy.second == wa * l.first + wb * l.second))
return {nowy.first * nowy.second, {wa, wb}};
auto left = rek(l, nowy);
auto right = rek(nowy, r);
ll prod_nowy = nowy.first * nowy.second;
return min({left, right, {prod_nowy, {wa, wb}}});
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
ll e;
cin >> n >> e;
edges.resize(e);
for (int i = 0; i < e; ++i) {
ll a, b, t, m;
cin >> a >> b >> t >> m;
edges[i] = {a, b, t, m};
}
rep.assign(n, 0);
sz.assign(n, 0);
auto l = mst(0, 1); // MST minimalizujący m
auto r = mst(1, 0); // MST minimalizujący t
auto ans = rek(l, r);
ll wa = ans.second.first, wb = ans.second.second;
auto final = mst(wa, wb);
cout << final.first << " " << final.second << "\n";
for (auto [a, b, t, m] : res) {
cout << a << " " << b << "\n";
}
return 0;
}
