Description

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.

Input Format

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$.

Output Format

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$.

4 5
0 1 1 2
0 2 2 3
0 3 1 5
1 3 3 4
2 3 1 3

3 10

Hint

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