Little A has a directed graph containing $$$N$$$ points and $$$M$$$ edges. For the $$$i$$$-th edge $$$(u_i, v_i)$$$, there are two attributes $$$(a_i, b_i)$$$.
A path P is defined as a directed path from point $$$1$$$ to point $$$N$$$, with its path weight given by: $$$$$$\left(\sum_{i \in P} a_i\right) \times \left(\sum_{i \in P} b_i\right)$$$$$$
Little A is very eager to know what the minimum weight is among all possible paths from node $$$1$$$ to node $$$N$$$. Please help him calculate this minimum product weight.
The first line contains a positive integer $$$T$$$ $$$(1\leq T\leq 10^3)$$$, indicating the number of test cases.
For each test case, the first line contains two integers $$$N,M$$$ $$$(1\leq N\leq 300,1 \leq M \leq 10^3)$$$, representing the number of points and edges in the graph, respectively.
The following $$$M$$$ lines each contain four integers $$$u_i,v_i,a_i,b_i$$$ $$$(1 \leq u_i,v_i \leq N,u_i\neq v_i,1\leq a_i,b_i \leq 200)$$$, representing the starting point, ending point, and weight attributes of a directed edge in the graph.
It is guaranteed that there exists at least one path from node 1 to node N.
It is guaranteed that the sum of $$$N$$$ in each test case does not exceed $$$10^3$$$, and the sum of $$$M$$$ does not exceed $$$2 \times 10^3$$$.
For each test case, output the values of $$$\sum_{i \in P} a_i$$$ and $$$\sum_{i \in P} b_i$$$ corresponding to the path with the minimum weight.
If there are multiple paths with the same minimum weight, please output the values corresponding to the path with the smallest $$$\sum_{i \in P} a_i$$$.
15 93 4 3 54 5 5 11 4 2 23 4 5 21 4 2 42 1 3 24 2 5 44 1 2 24 1 3 1
7 3
