解题思路

本题要求我们在一个给定的图中，找到在不同连通块数量下，最多可以删除红色边获得的权值总和。这涉及到图的连通性和最小生成树（MST）的问题。我们将通过最小生成树（MST）来最优化删除红色边的策略，以最大化我们能够获得的权值。

最小生成树的基本概念

最小生成树是一个图的子图，它包括图中所有的节点，并且使得所有的边的总权值最小。

问题转化为最小生成树

题目内容

小红有一张由 $n$ 个节点、$m$ 条边构成的图，每一条边都有一个权值，其中部分边被染成了红色，这些边是可以被删除的。对于每条染成红色的边，如果删除它，可以获得这条边的权值。

请你求出，对于每个 $k(1≤k≤n)$，在最终图的连通块数量不超过 $k$ 的条件下，小红最多能够获得的权值总和是多少。请依次输出 $k = 1,2,...,n$ 时的结果。

对于图上的两个点，如果它们之间有边相连，则称他们位于同一个连通块里。

输入描述

第一行包含两个整数 $n$ 和 $m(1 ≤ n,m ≤10^5)$，分别表示图中节点和边的数量。节点编号为 $1$ 到 $n$。 接下来 $m$ 行，第 $i$ 行输入四个整数

$u_i,v_i,w_i,c_i(1≤u_i,u_i≤n;1≤w_i<10^9;0≤c_i≤1)$代表第 $i$ 条边连接节点 $u_i$ 和 $v_i$，这条边的权值为 $w_i$ ，其中 $c_i= 1$ 表示该边被染成红色，$c_i=0$ 表示该边未被染色。

保证图中没有自环和重边，图初始是连通的。

输出描述

在一行上输出 $n$ 个整数，其中，第 $i$ 个整数代表当要求最终图的连通块数量小于等于 $i$ 时，小红最多能够获得的受益总和。

样例1

输入

4 4
1 2 5 1
2 3 3 0
3 4 4 1
1 4 2 1

输出

5 9 11 11

说明

删除第一条边，连通块数量为 $1$ ，权值总和为 $5$ 。

再删除第三条边，连通块数量为 $2$ ，权值总和为 $9$ 。

再删除第四条边，连通块数量为 $3$ ，权值总和为 $11$ 。

第二条边没有被染红，所以不会被删除。