P5540 [BalkanOI 2011] timeismoney

Given an undirected graph with $n$ vertices and $m$ edges, the $i$-th edge has two weights $a_i$ and $b_i$. Find a spanning tree $T$ of this graph such that $$\left(\sum_{e\in T}a_e\right)\times\left(\sum_{e\in T}b_e\right)$$ is minimized.

The first line contains two positive integers $n,m$. The next $m$ lines each contain $4$ integers $u_i,v_i,a_i,b_i$, meaning that the $i$-th edge connects $u_i$ and $v_i$, with weights $a_i$ and $b_i$. The vertices are numbered from $0$ to $n-1$.

Suppose the spanning tree you found is $T$. Output one line with two integers, which are $\displaystyle\sum_{e\in T}a_e$ and $\displaystyle\sum_{e\in T}b_e$. If there are multiple solutions, output the one with the smallest $\displaystyle\sum_{e\in T}a_e$.

For $100\%$ of the testdata, $1\leq n\leq 200$, $1\leq m\leq 10000$, $0\leq a_i,b_i\leq 255$. Translated by ChatGPT 5