连通能力

【题目描述】

对于一棵边上有权值的树（$N$个结点、$N-1$条边的无向连通图），我们按以下方法定义其连通能力： ①、规定某结点的代价为它到其它结点的距离（简单路径所经过边的权值和）的最大值。 ②、代价最小的结点的代价作为这棵树的连通能力。 设某棵给定的树以$1$号结点为根，求以任意结点为根的子树的连通能力有多大。

【输入】

第一行一个整数 $N$。 接下来$N-1$行，每行三个整数$u、v、w$，表示结点$u、v$间存在权值为 $w$的边。

【输出】

输出 $N$行$N$个整数，第$i$行的值表示以结点$i$为根的子树所对应的连通能力。

【输入样例】

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

【输出样例】

4
0
2
0
0

【提示】

【数据规模及约定】 对于20%的数据，$1≤N≤300$，所有边均与$1$号点相连。 对于40%的数据，$1≤N≤300$。 对于60%的数据，$1≤N≤4000$。 对于80%的数据，$1≤N≤100000$。 对于100%的数据，$1≤N≤1000000$，$1≤w≤10000$。