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.