Star 善于胡思乱想，这些天他又为带权树定义了一个叫"连通能力"的奇怪属性。对于一棵边上有权值的树（N 个
结点 N - 1 条边的无向连通图），我们按以下方法定义其连通能力：
1、规定某结点的代价为它到其它结点的距离（简单路径所经过边的权值和）的最大值；
2、代价最小的结点的代价作为这棵树的连通能力。
设某棵给定的树以 1 号结点为根，Star 想考察以任意结点为根的子树的连通能力有多大。
请你帮助他把这 N 个值快速求出来。
Input
第一行一个整数 N；
接下来 N - 1 行，每行三个整数 u、v、w 表示结点 u、v 间存在权值为 w 的边。
1 ≤ N ≤ 1000000、1 ≤ w ≤ 10000。
Output
输出 N 行 N 个整数，第 i 行的值表示以结点 i 为根的子树所对应的连通能力
input
6
1 2 2
1 3 8
2 4 4
2 5 6
4 6 3
output
9
7
0
3
0
0
/*
需要证明几个东西
1:以叶子点的根是树，答案是0
2: 对于非叶子点的树，答案必须是它的某个非叶子点
3:这个非叶子点在树的直径上,因为如果不在直径上，那么其必与直径上某个点a相连的，也必然没有a更优
4:树的直径可能并不经过根，直接从某个子树继承过来
5:所求的点在直径上,设直径的两个点为dep1[x],dep2[x]
呈现这样一种形式dep1[x].........j................dep2[x]
其中的j点，为一个我们从dep1[x]开始跳的点，尽量向右跳，但 [j,dep2[x]]>=[dep1[x],j]
这样跳出来后较大值始终为 [j,dep2[x]],但还有一种可能就是
dep1[x].........j...fa[j]............dep2[x]
值也可能为[dep1[x],fa[j],所以求两者的较小值
*/
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define L 25
#define N 1000005
#define M 2000005
using namespace std;
int t,first[N],v[M],w[M],nextt[M],father[N][L];
int d[N],r[N],f1[N],f2[N],dis[N],dep1[N],dep2[N];
void add(int x,int y,int z)
{
t++;
nextt[t]=first[x];
first[x]=t;
v[t]=y;
w[t]=z;
}
inline void getfather(int x)
{
int i,j;
for(i=first[x];i;i=nextt[i])
{
j=v[i];
if(j==father[x][0])
continue;
father[j][0]=x;
getfather(j);
}
}
inline void search(int x)
{
int i,j,depth;
dep1[x]=x;//x的最长链对应的端点
dep2[x]=x;//x的次长链对应的端点
for(i=first[x];i;i=nextt[i])
{
j=v[i];
if(j==father[x][0])
continue;
dis[j]=dis[x]+w[i];//j到根的距离
search(j);
if(r[j]>r[x])//直径在以j为根的子树中
{
d[x]=d[j];
r[x]=r[j];
}
if(f1[x]<f1[j]+w[i])//更新最长链及次长链及端点信息
{
f2[x]=f1[x];
dep2[x]=dep1[x];
f1[x]=f1[j]+w[i];
dep1[x]=dep1[j];
}
else if(f2[x]<f1[j]+w[i])
{
f2[x]=f1[j]+w[i];
dep2[x]=dep1[j];
}
}
depth=dep1[x];//从最长链的那个端点来跳
if(d[x]<f1[x]+f2[x])
{
d[x]=f1[x]+f2[x];
for(i=20;i>=0;--i)
if(depth!=x&&(f2[x]+dis[father[depth][i]]-dis[x]>=f1[x]-dis[father[depth][i]]+dis[x]))
//让depth尽量向上跳，所到的点必须满足[次长链端点,所跳点]>=[最长链端点,所跳点]
depth=father[depth][i];
r[x]=f2[x]+dis[depth]-dis[x];
//dep1[x].........x.......x的父亲点.......dep2[x]
//所求半径可能为[x,dep2[x]
if(depth!=x&&f1[x]-dis[father[depth][0]]+dis[x]<r[x])
//所求半径也可能为[dep1[x],x的父亲点],应取其中的较小值
r[x]=f1[x]-dis[father[depth][0]]+dis[x];
}
}
int main()
{
int n,i,j,x,y,z;
scanf("%d",&n);
for(i=1;i<n;++i)
{
scanf("%d%d%d",&x,&y,&z);
add(x,y,z);
add(y,x,z);
}
getfather(1);
for(j=1;j<=20;++j)
for(i=1;i<=n;++i)
father[i][j]=father[father[i][j-1]][j-1];
search(1);
for(i=1;i<=n;++i)
cout<<r[i]<<'\n';
return 0;
}
//*
6
1 2 2
1 3 8
2 4 4
2 5 6
4 6 3
9
7
0
3
0
0
//