#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 time = 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)) { time += t; money += m; res.push_back({a,b,t,m}); } } return {time, money}; } pair<ll, pair<ll, ll>> rek(ll x1, ll y1, ll x2, ll y2) { ll a = abs(y2-y1); ll b = abs(x1-x2); auto[t,m] = mst(a,b); if(a*t + b*m == a*x1 + b*y1) return {t*m, {a,b}}; pair<ll, pair<ll, ll>> a1 = rek(x1,y1,t,m); pair<ll, pair<ll, ll>> a2 = rek(t,m,x2,y2); return min(min(a1,a2), {t*m, {a,b}}); } 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); pair<ll, pair<ll, ll>> ans = rek(t1,m1,t2,m2); ans = min(ans, {t1*m1, {0,1}}); ans = min(ans, {t2*m2, {1,0}}); 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; }