Problem Description

Link hates running.

Today, Link is asked to run. Roads in BIT can be described as $n$ nodes and $m$ directed edges. Link has to run from node $1$ to node $n$. When Link is at node $u_i$, he can run through the $i$-th edge to get to node $v_i$. Every time he runs through the $i$-th edge, he spends $e_i$ points of energy and gains $p_i$ points of physical fitness.

As a lazy boy, Link wants to spend as little energy as possible. He is also greedy and wants to gain maximum physical fitness when spending minimum energy.

Tell Link the minimum energy $min_e$ he needs to spend and the maximum physical fitness $max_p$ he can gain when spending the minimum energy.

Input

Each test contains multiple test cases. The first line contains the number of test cases $T(1 \le T \le 12)$. Description of the test cases follows.

The first line contains two integers $n,m(2 \leq n \leq 10^5, 1 \leq m \leq 3 \times 10^5)$, which are the number of nodes and the number of edges.

Each of the next $m$ lines contains four integers $u_i,v_i,e_i,p_i(1 \leq u_i,v_i \leq n, 0 \leq e_i,p_i \leq 10^9$), describing an edge.

Output

For each test case, output $min_e$ and $max_p$ in a single line, separated by one space.

It is guaranteed that THE ANSWER EXISTS and CAN BE REPRESENTED AS A NUMBER.

2
3 3
1 2 1 1
2 3 1 1
1 3 2 0
3 3
1 2 1 1
2 3 1 1
1 3 1 0

2 2
1 0