Migrated from Lutece 2761 桥梁装饰

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

$A$ 城与 $B$ 城之间修建了一座拱桥，现在为了夜晚的照明，要在桥上加上一些灯带。这座拱桥可以视为带有 $10^6$ 个点的拱形，标号从 $1$ 到 $10^6$。上面有 $N$ 条灯带，第 $i$ 条灯带从 $x_i$ 这个端点连接到 $y_i$ 端点，并有一个亮度值 $v_i$，可以选择点亮或不点亮。

为了避免不必要的安全问题，没有两条两个端点重复的灯带，且任意两条灯带只会在端点处相交。如：$(1,3)$ 和 $(2,3)$ 和 $(3,4)$ 是可以同时存在的，但 $(1,3)$ 和 $(2,4)$ 不能同时存在，因为两者在端点处以外的地方相交了。

现在定义一个点的危险系数为，所有覆盖这个点且不以这个点作为端点的点亮的灯带数。如：点亮 $(2,4)$ 这条灯带使 $3$ 点的危险系数提高 $1$，但不影响 $2$ 和 $4$ 的危险系数。整座桥梁的危险系数为这 $10^6$ 个点的危险系数的最大值，桥梁的亮度值为所有点亮的灯带的亮度之和。

你的任务是对于所有的 $1 \le K \le N$ 求出在桥梁安全系数小于等于 $K$ 时的最大桥梁亮度值。

Input

第 $1$ 行一个整数 $N$，表示灯带的数量
第 $2$ 到 $N+1$ 行每行三个整数 $x_i,y_i,v_i$ 表示灯带的两个端点和亮度值

Output

输出一行 $N$ 个整数表示答案，空格隔开

Samples

7
1 3 1
1 2 10
2 3 100
3 5 1000
5 7 10000
1 5 100000
1 7 1000000

1000000 1110000 1111110 1111111 1111111 1111111 1111111

Constraints

$1 \le N \le 250000$, $1 \le x_i < y_i \le 10^6 , 1 \le v_i \le 10^9$

Resources

2022 UESTC ICPC Training for Data Structures