问题描述

给定一张 $n$ 个点 $m$ 条边的 无向连通图，图中的第 $i$ 条边有 $a_i,b_i$ 两个权重。

对于图中的每条边，你可以选择 $a_i,b_i$ 其中之一作为该条边的边权。

对于所有满足 $0\le k\le m$ 的整数 $k$，你需要求出，若选择 恰好 $k$ 个 $a_i$ 作为对应边的边权，恰好 $m-k$ 个 $b_i$ 作为对应边的边权，该图的最小生成树的边权和 最大 是多少。

输入格式

第一行包含两个整数 $n,m$。

接下来 $m$ 行，每行包含四个整数 $x_i,y_i,a_i,b_i$，表示图中的第 $i$ 条边，其连接 $x_i,y_i$ 两点，权重为 $a_i,b_i$。

输出格式

输出 $m+1$ 行共 $m+1$ 个整数，第 $i$ 个数表示 $k=i-1$ 时的答案。

输入样例1

3 3
1 2 5 4
2 3 2 9
1 3 3 6

输出样例1

10
11
8
5

样例1解释

$k=0$：选择 $b_1,b_2,b_3$，最小生成树边权和为 $b_1+b_3=10$。

$k=1$：选择 $a_1,b_2,b_3$，最小生成树边权和为 $a_1+b_3=11$。

$k=2$：选择 $a_1,b_2,a_3$，最小生成树边权和为 $a_1+a_3=8$。

$k=3$：选择 $a_1,a_2,a_3$，最小生成树边权和为 $a_2+a_3=5$。

数据范围

对于所有数据，保证 $2\le n\le 9$，$n-1\le m\le 100$，$1\le x_i,y_i\le n$，$1\le a_i,b_i\le 10^8$。保证图连通且无自环。