Spanning Tree Game

Alice and Bob are playing a game on an undirected graph with $n$ vertices and $m$ edges. The vertices are labeled by $1,2,\dots,n$. The edges are labeled by $1,2,\dots,m$. The $i$-th edge connects the $u_i$-th vertex and the $v_i$-th vertex directly, and its weight will be chosen from the given two values $a_i$ and $b_i$.

First, Alice needs to assign weights to all the $m$ 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,\dots,m$ if both of the players play optimally.

The first line contains a single integer $T$ ($1 \leq T \leq 20$), the number of test cases. For each test case:

The first line contains two integers $n$ and $m$ ($2 \leq n \leq 9$, $n-1\leq m\leq 30$), denoting the number of vertices and the number of edges.

Each of the following $m$ lines contains four integers $u_i,v_i,a_i$ and $b_i$ ($1 \leq u_i,v_i \leq n$, $u_i\neq v_i$, $1\leq a_i,b_i\leq 1\,000\,000$), describing an edge.

It is guaranteed that the graph is connected.

For each test case, output $m+1$ lines, the $i$-th ($1\leq i\leq m+1$) of which containing an integer, denoting the final score when $k=i-1$.

1
3 3
1 2 4 6
1 3 2 7
2 3 3 5

11
9
7
5

2022“杭电杯”中国大学生算法设计超级联赛（3）