题目描述

对于一棵边上有权值的树（$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$。

评测数据说明

本题使用按题意独立构造、以独立程序核对的训练数据及公开样例，共8个测试点，非原站或官方原始数据。总分100分。