Alice and Bob are playing a game on an undirected graph with n vertices and mm edges. The vertices are labeled by 1,2,…,n. The edges are labeled by 1,2,…,m. The ii-th edge connects the ui-th vertex and the vi-th vertex directly, and its weight will be chosen from the given two values ai and bi.
First, Alice needs to assign weights to all the mm edges such that there are exactly k edges whose weights are taken from a while the weights of other m-k edges are taken from b. Then, Bob needs to choose exactly n-1 edges from the graph such that every pair of different vertices are connected by these n-1 edges directly or indirectly.
The final score of the game is equal to the total weights of the n-1 edges chosen by Bob. Alice wants to maximize the score while Bob wants to minimize it. Please write a program to predict the final score for k=0,1,2,…,m if both of the pla
The first line contains a single integer T(1≤T≤20), the number of test cases. For each test case:
The first line contains two integers n and m (2≤n≤9,n−1≤m≤30), denoting the number of vertices and the number of edges.
Each of the following mm lines contains four integers ui,vi,ai and bi (1≤ui,vi≤n, 1≤ai,bi≤1,000,000), describing an edge.
It is guaranteed that the graph is connected.
1
3 3
1 2 4 6
1 3 2 7
2 3 3 511
9
7
5