The beautiful country of Thuvax has an ancient rail network connecting its 'n' cities using 'm' tracks. The King of Thuvax orders the Railway Minister, Poopsie to renovate the whole rail network. Due to Poopsie's past laziness, the tracks are in shambles and so he wants to rebuild (the tracks are functional again) some of the tracks and destruct (therefore, wont be available for usage) the rest completely.
 
The King wants to ensure that all the cities are connected after the whole network is renovated but being a miser, he wants to spend the least amount of money possible.  

Help Poopsie find out the least amount of money using which the renovation project can be completed.

Input

The first line of the input contains the number of test cases 't' (1<=t<=100).
 
The first line of each test case consists of two numbers: number of cities 'n' (1<=n<=10^3) and number of tracks 'm' (0<=m<=10^6).
The next m lines contains description of each of the tracks and their corresponding costs of destruction and rebuilding.
Each of these m lines contains four integers 'a', 'b', 'd' and 'r' (1<=d, r<=1000000) representing a track between city 'a' and city 'b' with the cost of destruction and rebuilding being d and r respectively (cities are numbered from 1 to n).

Output

The output consists of t lines.

For each test case, print a single line consisting of a single integer that is the least amount of the money required to renovate the whole rail network.

Example

Input:
1 
4 4 
2 1 7 8 
3 2 4 6 
4 2 2 4 
1 4 3 5

Output:
21