KNN
题号：NC281336
时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

邻近算法，或者说K最邻近（KNN，K-NearestNeighbor）分类算法是数据挖掘分类技术中最简单的方法之一。
所谓K最近邻，就是K个最近的邻居的意思，说的是每个样本都可以用它最接近的K个邻近值来代表。
近邻算法就是将数据集合中每一个记录进行分类的方法。
当然，xcpc 选手大概率不想看上面的题目背景，KNN 实际上就是花费最少的代价，建立 n-k 条无向边，让 n 个节点连接成 k 个连通块。
注意到 k=1 时，这是一棵 最小生成树。
由于KNN的点集分类不唯一，懒比76也不想写spj，所以他想请你分别输出 k=1,2,3, \cdots ,n 的最小代价。

输入描述:

第一行有一个整数 n\ (\ 2 \leq n \leq 10^3\ ) ，代表节点的总数。
随后 n \cdot (n-1)/2 行，每行三个整数 u,v,w\ (\ 1 \leq u \lt v \leq n\ )\ ,\ (\ 1 \leq w \leq 10^9\ ) ，代表 u 和 v 之间有一条代价为 w 的无向边。
保证没有重边和自环。

输出描述:

在一行内输出 n 个整数，代表 k=1,2,3, \cdots ,n 的最小代价。
示例1

输入

复制 
3
1 2 1
1 3 2
2 3 4

输出

复制 
3 1 0

说明

当 k=1 时，我们选择代价较少的 2 条边，代价为 3 。
当 k=2 时，我们选择代价较少的 1 条边，代价为 1 。
当 k=3 时，我们不需要选择任何一条边 ，代价为 0 。

备注:

这是一张KNN的示意图，与样例无关。