#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define fi first
#define se second
#define For(i, l, r) for (auto i = (l); i < (r); i++)
#define ForE(i, l, r) for (auto i = (l); i <= (r); i++)
#define FordE(i, l, r) for (auto i = (l); i >= (r); i--)
#define Fora(v, a) for (auto v: (a))
#define bend(a) (a).begin(), (a).end()
#define isz(a) ((signed)(a).size())
using ll = long long;
using ld = long double;
using pii = pair <int, int>;
using vi = vector <int>;
using vpii = vector <pii>;
using vvi = vector <vi>;
template<bool Enable_small_to_large = true>
struct disjoint_set{
int n, _classes;
vector<int> p;
disjoint_set(int n): n(n), _classes(n), p(n, -1){ }
int make_set(){
p.push_back(-1);
++ _classes;
return n ++;
}
int classes() const{
return _classes;
}
int root(int u){
return p[u] < 0 ? u : p[u] = root(p[u]);
}
bool share(int a, int b){
return root(a) == root(b);
}
int size(int u){
return -p[root(u)];
}
bool merge(int u, int v){
u = root(u), v = root(v);
if(u == v) return false;
-- _classes;
if constexpr(Enable_small_to_large) if(p[u] > p[v]) swap(u, v);
p[u] += p[v], p[v] = u;
return true;
}
bool merge(int u, int v, auto act){
u = root(u), v = root(v);
if(u == v) return false;
-- _classes;
bool swapped = false;
if constexpr(Enable_small_to_large) if(p[u] > p[v]) swap(u, v), swapped = true;
p[u] += p[v], p[v] = u;
act(u, v, swapped);
return true;
}
void clear(){
_classes = n;
fill(p.begin(), p.end(), -1);
}
vector<vector<int>> group_up(){
vector<vector<int>> g(n);
for(auto i = 0; i < n; ++ i) g[root(i)].push_back(i);
g.erase(remove_if(g.begin(), g.end(), [&](auto &s){ return s.empty(); }), g.end());
return g;
}
};
struct edge{
int u, v, x, y;
};
ll eval(const pair <pii, vpii>& ans){
return (ll)ans.fi.fi * ans.fi.se;
}
const int inf = 1e9 + 7;
int n, m;
vector <edge> a;
disjoint_set dsu(n);
pair <pii, vpii> ans = {pair{inf, inf}, vpii{}};
pair <pii, vpii> find_mst(int cx, int cy){
sort(bend(a), [&](const edge& lhs, const edge& rhs){
return lhs.x * cx + lhs.y * cy < rhs.x * cx + rhs.y * cy;
});
pair <pii, vpii> tans = {pair{0, 0}, vpii{}};
dsu.clear();
for (auto &[u, v, x, y]: a){
if (dsu.merge(u, v)){
tans.fi.fi += x; tans.fi.se += y;
tans.se.emplace_back(u, v);
}
}
if (eval(ans) > eval(tans)){
ans = tans;
}
return tans;
}
void recurse(const pii& p1, const pii& p2){
pii slope = {p2.se - p1.se, p2.fi - p1.fi};
pii p3 = find_mst(-slope.fi, slope.se).fi;
if (p3 == p1 or p3 == p2){
return;
}
pii slope2 = {p2.se - p3.se, p2.fi - p3.fi};
if ((ll)slope.fi * slope2.se == (ll)slope2.fi * slope.se){
return;
}
recurse(p1, p3);
recurse(p3, p2);
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
// freopen("timeismoney.in", "r", stdin);
// freopen("timeismoney.out", "w", stdout);
cin >> n >> m;
For(i, 0, m){
int u, v, x, y; cin >> u >> v >> x >> y;
a.emplace_back(u, v, x, y);
}
dsu = disjoint_set(n);
pii p1 = find_mst(1, 0).fi;
pii p2 = find_mst(0, 1).fi;
recurse(p1, p2);
cout << ans.fi.fi << ' ' << ans.fi.se << endl;
for (auto &[u, v]: ans.se){
cout << u << ' ' << v << endl;
}
}
/*
==================================================+
INPUT |
--------------------------------------------------|
--------------------------------------------------|
==================================================+
OUTPUT |
--------------------------------------------------|
--------------------------------------------------|
==================================================+
*/
Compilation message
timeismoney.cpp:51:30: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
51 | bool merge(int u, int v, auto act){
| ^~~~
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/c++allocator.h:33,
from /usr/include/c++/10/bits/allocator.h:46,
from /usr/include/c++/10/string:41,
from /usr/include/c++/10/bits/locale_classes.h:40,
from /usr/include/c++/10/bits/ios_base.h:41,
from /usr/include/c++/10/ios:42,
from /usr/include/c++/10/istream:38,
from /usr/include/c++/10/sstream:38,
from /usr/include/c++/10/complex:45,
from /usr/include/c++/10/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
from timeismoney.cpp:1:
/usr/include/c++/10/ext/new_allocator.h: In instantiation of 'void __gnu_cxx::new_allocator<_Tp>::construct(_Up*, _Args&& ...) [with _Up = edge; _Args = {int&, int&, int&, int&}; _Tp = edge]':
/usr/include/c++/10/bits/alloc_traits.h:512:17: required from 'static void std::allocator_traits<std::allocator<_CharT> >::construct(std::allocator_traits<std::allocator<_CharT> >::allocator_type&, _Up*, _Args&& ...) [with _Up = edge; _Args = {int&, int&, int&, int&}; _Tp = edge; std::allocator_traits<std::allocator<_CharT> >::allocator_type = std::allocator<edge>]'
/usr/include/c++/10/bits/vector.tcc:115:30: required from 'std::vector<_Tp, _Alloc>::reference std::vector<_Tp, _Alloc>::emplace_back(_Args&& ...) [with _Args = {int&, int&, int&, int&}; _Tp = edge; _Alloc = std::allocator<edge>; std::vector<_Tp, _Alloc>::reference = edge&]'
timeismoney.cpp:130:34: required from here
/usr/include/c++/10/ext/new_allocator.h:150:4: error: new initializer expression list treated as compound expression [-fpermissive]
150 | { ::new((void *)__p) _Up(std::forward<_Args>(__args)...); }
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/10/ext/new_allocator.h:150:4: error: no matching function for call to 'edge::edge(int&)'
timeismoney.cpp:73:8: note: candidate: 'edge::edge()'
73 | struct edge{
| ^~~~
timeismoney.cpp:73:8: note: candidate expects 0 arguments, 1 provided
timeismoney.cpp:73:8: note: candidate: 'constexpr edge::edge(const edge&)'
timeismoney.cpp:73:8: note: no known conversion for argument 1 from 'int' to 'const edge&'
timeismoney.cpp:73:8: note: candidate: 'constexpr edge::edge(edge&&)'
timeismoney.cpp:73:8: note: no known conversion for argument 1 from 'int' to 'edge&&'
