分析
我们可以把每棵生成树的 $\displaystyle\sum_{e\in T}a_e$ 和 $\displaystyle\sum_{e\in T}b_e$ 看做二维坐标 $(x,y)$ 。于是我们就相当于要找一个 $x\times y$ 最小的点。
这个东西可以分三步求：
求出与 $x$ 轴和 $y$ 轴最近的点
这个还是很简单的。
把 $a_i$ 作为边权，求出的最小生成树就是与 $x$ 轴最近的点。
把 $b_i$ 作为边权，求出的最小生成树就是与 $y$ 轴最近的点。
为了下面讲解的方便，设与 $x$ 轴最近的点为 $A$ ，与 $y$ 轴最近的点为 $B$ 。
找到一个在 $AB$ 的左下方且离 $AB$ 最远的点
可能有一点难度。
假设这个点是 $C$ ，那么大概是这个样子：
事实上，$C$ 就是在 $AB$ 的左下方且 $S_{\triangle ABC}$ 最大的点。
容易知道 $S_{\triangle ABC}=-\frac{\vec{AB}\times\vec{AC}}{2}$ 。于是我们只要最小化 $\vec{AB}\times\vec{AC}$ 即可。
推一推式子：
$$
\begin{aligned}\vec{AB}\times\vec{AC}&=(x_B-x_A)(y_C-y_A)-(x_C-x_A)(y_B-y_A)\\&=(x_B-x_A)y_C-(x_B-x_A)y_A-(y_B-y_A)x_C+(y_B-y_A)x_A\\&=(x_B-x_A)y_C+(y_A-y_B)x_C-(x_B-x_A)y_A+(y_B-y_A)x_A\end{aligned}
$$
后两项是常数，我们只需最小化前两项。于是将边权设为 $(x_B-x_A)b_i+(y_A-y_B)a_i$ ，然后求最小生成树即可。
递归处理 $AC$ 与 $BC$
把当前 $AC$ 和 $BC$ 拿去做第二步的过程即可。
当新算出的 $C$ 不在 $AB$ 的左下方时就可以终止了。
代码
//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
typedef long long ll;
using namespace std;
inline int rd() {
int X=0,w=1; char c=getchar();
while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
return X*w;
}
const int N=200+10;
const int M=10000+10;
const int inf=0x3f3f3f3f;
struct UFS {
int f[N];
inline void init(int n) { for (re int i=1;i<=n;++i) f[i]=i; }
inline int find(int x) { return x==f[x]?x:f[x]=find(f[x]); }
inline void merge(int x,int y) { x=find(x),y=find(y); if (x!=y) f[x]=y; }
inline int check(int x,int y) { return find(x)==find(y); }
};
struct Edge { int u,v,w,c,t; };
inline int cmp(Edge a,Edge b) {
return a.w<b.w;
}
struct Point { int x,y; };
typedef Point Vector;
Vector operator -(Point a,Point b) { return (Point){a.x-b.x,a.y-b.y}; }
inline int cross(Vector a,Vector b) { return a.x*b.y-a.y*b.x; }
int n,m;
UFS S;
Point ans=(Point){inf,inf};
Edge e[M];
inline Point Kruskal() {
Point res=(Point){0,0}; int tot=0;
sort(e+1,e+m+1,cmp); S.init(n);
for (re int i=1;i<=m;++i) {
int u=e[i].u,v=e[i].v,c=e[i].c,t=e[i].t;
if (S.check(u,v)) continue;
S.merge(u,v),res.x+=c,res.y+=t,++tot;
if (tot==n-1) break;
}
/*顺便更新答案*/
ll Ans=1ll*ans.x*ans.y,now=1ll*res.x*res.y;
if (Ans>now||(Ans==now&&ans.x>res.x)) ans=res;
return res;
}
inline void solve(Point A,Point B) {
for (re int i=1;i<=m;++i) e[i].w=e[i].t*(B.x-A.x)+e[i].c*(A.y-B.y);
Point C=Kruskal();
if (cross(B-A,C-A)>=0) return;
solve(A,C),solve(C,B);
}
int main() {
n=rd(),m=rd();
for (re int i=1;i<=m;++i)
e[i].u=rd()+1,e[i].v=rd()+1,e[i].c=rd(),e[i].t=rd();
for (re int i=1;i<=m;++i) e[i].w=e[i].c;
Point A=Kruskal();
for (re int i=1;i<=m;++i) e[i].w=e[i].t;
Point B=Kruskal();
solve(A,B); printf("%d %d\n",ans.x,ans.y);
return 0;
}