8511: link with Running

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 ui, he can run through the ith edge to get to node vi. Every time he runs through the ith edge, he spends ei points of energy and gains pi 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 mine he needs to spend and the maximum physical fitness maxp he can gain when spending the minimum energy.

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≤n≤105,1≤m≤3×105), which are the number of nodes and the number of edges.

Each of the next $m$ lines contains four integers ui,vi,ei,pi(1≤ui,vi≤n,0≤ei,pi≤109), describing an edge.

For each test case, output min_emine and max_pmaxp 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