#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; }