Alice 和 Bob 在一个具有 $n$ 个顶点和 $m$ 条边的无向图上玩游戏。顶点编号为 $1, 2, \dots, n$，边编号为 $1, 2, \dots, m$。第 $i$ 条边直接连接 $u_i$ 号顶点和 $v_i$ 号顶点，其权重将从给定的两个值 $a_i$ 和 $b_i$ 中选择。

首先，Alice 需要为所有 $m$ 条边分配权重，使得恰好有 $k$ 条边的权重取自 $a$，而其余 $m - k$ 条边的权重取自 $b$。然后，Bob 需要从图中选择恰好 $n - 1$ 条边，使得任意两个不同的顶点都能通过这 $n - 1$ 条边直接或间接地连通。

游戏的最终得分等于 Bob 所选的 $n - 1$ 条边的权重之和。Alice 希望最大化该得分，而 Bob 希望最小化该得分。请编写一个程序，预测当 $k = 0, 1, 2, \dots, m$ 时，若双方均采取最优策略，游戏的最终得分。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 20$)，表示测试用例的数量。对于每个测试用例： 第一行包含两个整数 $n$ 和 $m$ ($2 \le n \le 9, n-1 \le m \le 30$)，分别表示顶点数和边数。 接下来的 $m$ 行，每行包含四个整数 $u_i, v_i, a_i$ 和 $b_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i, 1 \le a_i, b_i \le 1\,000\,000$)，描述一条边。

保证图是连通的。

输出格式

对于每个测试用例，输出 $m + 1$ 行，其中第 $i$ 行 ($1 \le i \le m + 1$) 包含一个整数，表示当 $k = i - 1$ 时的最终得分。

样例

样例输入 1

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

样例输出 1

11
9
7
5