#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; template <typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; struct Edge { ll a, b, t, m; }; int n; vector<Edge> edges; vector<ll> rep, sajz; 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 0; if(sajz[b] > sajz[a]) swap(a,b); rep[b] = a; sajz[a] += sajz[b]; return 1; } vector<Edge> res; pair<ll, ll> mst(ll wsp1, ll wsp2) { while(res.size()) res.pop_back(); for(ll i=0; i<n; ++i) rep[i] = i; for(ll i=0; i<n; ++i) sajz[i] = 1; ll czas = 0; ll money = 0; sort(edges.begin(), edges.end(), [&](Edge x, Edge y) { ll v1 = wsp1*x.t + wsp2*x.m; ll v2 = wsp1*y.t + wsp2*y.m; return v1 < v2; }); 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}; } vector<pair<ll, pair<ll, ll>>> odp; void rek(ll x1, ll y1, ll x2, ll y2) { ll a = y2-y1; ll b = x1-x2; auto[t,m] = mst(a,b); odp.push_back({t*m, {a,b}}); if((t==x1 && m==y1) || (t==x2 && m==y2) || (a*t + b*m == a*x1 + b*y1)) return; rek(x1,y1,t,m); rek(t,m,x2,y2); } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); ll e; cin >> n >> e; for(ll i=0; i<e; ++i) { ll a, b, m, t; cin >> a >> b >> t >> m; edges.push_back({a,b,t,m}); } rep.assign(n,0); sajz.assign(n,0); auto[t1,m1] = mst(0,1); auto[t2,m2] = mst(1,0); rek(t1,m1,t2,m2); odp.push_back({t1*m1, {0,1}}); odp.push_back({t2*m2, {1,0}}); ll inf = 1e18; pair<ll, pair<ll, ll>> ans = {inf, {0,0}}; for(auto x : odp) ans = min(ans, x); auto[val, para] = ans; auto[a,b] = para; auto[t,m] = mst(a,b); cout << t << " " << m << "\n"; for(auto[a,b,t,m] : res) cout << a << " " << b << "\n"; return 0; }