#pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #include <bits/stdc++.h> using namespace std; #define pb push_back #define all(a) a.begin(),a.end() typedef long long ll; typedef pair<int,int> pii; typedef pair<ll,ll> pll; typedef unsigned long long ull; typedef vector<int> vi; const int mxn = 200, mxm = 10000; short par[mxn]; vector<array<short,4>> edges; short get(short u){return (par[u]<0?u:par[u]=get(par[u]));} int n,m; int timeismoney = 2e9; pii timexmoney = {1,0}; pii oracle(int a, int b){ sort(all(edges),[&](const array<short,4> &A, const array<short,4> &B){ return A[3]*a + A[2]*b < B[3]*a + B[2]*b; }); fill(par,par+n,-1); int time = 0, money = 0; for(const auto &[u,v,t,c] : edges){ if(get(u)==get(v)); else par[get(v)] = get(u), time += t, money += c; } if(timeismoney > time*money){ timeismoney = time*money; timexmoney = {time,money}; } return {time,money}; } void divide(const pii &l, const pii &r){ int a = l.first - r.first, b = r.second - l.second; auto [x,y] = oracle(a,b); if(x*b + y*a == b*l.first + a*l.second) return; divide(l,{x,y}); divide({x,y},r); } void solve(){ cin >> n >> m; edges.resize(m); for(auto &[u,v,t,c] : edges) cin >> u >> v >> t >> c; auto l = oracle(1,0); auto r = oracle(0,1); divide(l,r); fill(par,par+n,-1); sort(all(edges),[&](const array<short,4> &A, const array<short,4> &B){ return A[3]*timexmoney.first + A[2]*timexmoney.second < B[3]*timexmoney.first + B[2]*timexmoney.second; }); cout << timexmoney.first << ' ' << timexmoney.second << '\n'; for(const auto &[u,v,t,c] : edges){ if(get(u)==get(v)); else par[get(v)] = get(u), cout << u << ' ' << v << '\n'; } } signed main(){ cin.tie(0)->sync_with_stdio(0); int t = 1; // cin >> t; while(t--){solve();} }