#include<iomanip>
#include<limits>
#include<thread>
#include<utility>
#include<iostream>
#include<string>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<stack>
#include<queue>
#include<cmath>
#include<numeric>
#include<cassert>
#include<random>
#include<chrono>
#include<unordered_map>
#include<fstream>
#include<list>
using namespace std;
typedef unsigned long long int ull;
typedef long long int ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pi;
typedef pair<double,double> pd;
typedef pair<double,ll> pdl;
#define F first
#define S second
const ll E=1e18+7;
const ll MOD=1000000007;

class weight_LCA{
private:
    typedef pair<ll,vector<pll>> node; //depth,parents,cost
    ll root;
    ll v;
    vector<node> tree;
    vector<vector<pll>> E; //to,cost
    ll High; //高さのlog
    
    void bfs(){
        tree[root]={0,{{root,0}}};
        queue<ll> q;
        q.push(root);
        vector<bool> done(v,false);
        while(!q.empty()){
            ll where=q.front();
            q.pop();
            if(done[where]){continue;}
            done[where]=true;
            for(int i=0;i<E[where].size();i++){
                if(!done[E[where][i].F]){
                    tree[E[where][i].F].F=tree[where].F+1;
                    tree[E[where][i].F].S={{where,E[where][i].S}};
                    q.push(E[where][i].F);
                }
            }
        }
    }
    
public:
    weight_LCA(ll v,ll root):v(v),root(root){
        tree.resize(v);
        E.resize(v);
    }
    
    //双方向のエッジでもよい
    void add_edge(ll from,ll to,ll cost){
        E[from].push_back({to,cost});
    }
    
    //searchの前に行う
    void mk_tree(){
        bfs();
        bool j=true;
        for(int i=0;j;i++){
            j=false;
            for(int t=0;t<v;t++){
                ll cost=tree[t].S[i].S;
                ll P=tree[t].S[i].F;
                cost+=tree[P].S[i].S;
                P=tree[P].S[i].F;
                tree[t].S.push_back({P,cost});
                if(P!=root){j=true;}
            }
        }
        High=tree[root].S.size();
    }
    
    //parent,cost
    pll search_parent(ll a,ll h){
        if(tree[a].F<=h){return {root,tree[a].S[High-1].S};}
        ll cost=0;
        for(ll i=High-1;i>=0;i--){
            if((1<<i)&h){
                cost+=tree[a].S[i].S;
                a=tree[a].S[i].F;
            }
        }
        return {a,cost};
    }
    
    //parent,a_cost_b_cost
    pair<ll,pll> search_lca(ll a,ll b){
        ll dif=tree[a].F-tree[b].F;
        ll a_cost=0;
        ll b_cost=0;
        if(0>dif){
            pll k=search_parent(b,-1*dif);
            b=k.F;
            b_cost+=k.S;
        }
        else{
            pll k=search_parent(a,dif);
            a=k.F;
            a_cost+=k.S;
        }
        for(ll i=High-1;i>=0;i--){
            if(tree[a].S[i].F!=tree[b].S[i].F){
                a_cost+=tree[a].S[i].S;
                a=tree[a].S[i].F;
                b_cost+=tree[b].S[i].S;
                b=tree[b].S[i].F;
            }
        }
        while(a!=b){
            a_cost+=tree[a].S[0].S;
            a=tree[a].S[0].F;
            b_cost+=tree[b].S[0].S;
            b=tree[b].S[0].F;
        }
        return {a,{a_cost,b_cost}};
    }
    
    
    ll high(ll a){
        return tree[a].F;
    }
};

ll cost(pair<ll,pll> P){
    return P.S.F+P.S.S;
}



int main(){
    ll n;
    cin>>n;
    weight_LCA lca(n,0);
    for(int i=0;i<n-1;i++){
        ll s,t,w;
        cin>>s>>t>>w;
        lca.add_edge(s,t,w);
        lca.add_edge(t,s,w);
    }
    lca.mk_tree();
    ll A=0;
    ll mx=0;
    for(int i=1;i<n;i++){
        ll c=cost(lca.search_lca(0,i));
        if(c>mx){mx=c; A=i;}
    }
    ll B=A;
    mx=0;
    for(int i=0;i<n;i++){
        ll c=cost(lca.search_lca(A,i));
        if(c>mx){mx=c; B=i;}
    }
    for(int i=0;i<n;i++){
        cout<<max(cost(lca.search_lca(A,i)),cost(lca.search_lca(B,i)))<<endl;
    }
    
    
    return 0;
}


### Prompt

Develop a solution in CPP to the problem described below:

Given a tree T with non-negative weight, find the height of each node of the tree. For each node, the height is the distance to the most distant leaf from the node.

Constraints

* 1 ≤ n ≤ 10,000
* 0 ≤ wi ≤ 1,000

Input


n
s1 t1 w1
s2 t2 w2
:
sn-1 tn-1 wn-1


The first line consists of an integer n which represents the number of nodes in the tree. Every node has a unique ID from 0 to n-1 respectively.

In the following n-1 lines, edges of the tree are given. si and ti represent end-points of the i-th edge (undirected) and wi represents the weight (distance) of the i-th edge.

Output

The output consists of n lines. Print the height of each node 0, 1, 2, ..., n-1 in order.

Example

Input

4
0 1 2
1 2 1
1 3 3


Output

5
3
4
5

### Response

```cpp
#include<iomanip>
#include<limits>
#include<thread>
#include<utility>
#include<iostream>
#include<string>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<stack>
#include<queue>
#include<cmath>
#include<numeric>
#include<cassert>
#include<random>
#include<chrono>
#include<unordered_map>
#include<fstream>
#include<list>
using namespace std;
typedef unsigned long long int ull;
typedef long long int ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pi;
typedef pair<double,double> pd;
typedef pair<double,ll> pdl;
#define F first
#define S second
const ll E=1e18+7;
const ll MOD=1000000007;

class weight_LCA{
private:
    typedef pair<ll,vector<pll>> node; //depth,parents,cost
    ll root;
    ll v;
    vector<node> tree;
    vector<vector<pll>> E; //to,cost
    ll High; //高さのlog
    
    void bfs(){
        tree[root]={0,{{root,0}}};
        queue<ll> q;
        q.push(root);
        vector<bool> done(v,false);
        while(!q.empty()){
            ll where=q.front();
            q.pop();
            if(done[where]){continue;}
            done[where]=true;
            for(int i=0;i<E[where].size();i++){
                if(!done[E[where][i].F]){
                    tree[E[where][i].F].F=tree[where].F+1;
                    tree[E[where][i].F].S={{where,E[where][i].S}};
                    q.push(E[where][i].F);
                }
            }
        }
    }
    
public:
    weight_LCA(ll v,ll root):v(v),root(root){
        tree.resize(v);
        E.resize(v);
    }
    
    //双方向のエッジでもよい
    void add_edge(ll from,ll to,ll cost){
        E[from].push_back({to,cost});
    }
    
    //searchの前に行う
    void mk_tree(){
        bfs();
        bool j=true;
        for(int i=0;j;i++){
            j=false;
            for(int t=0;t<v;t++){
                ll cost=tree[t].S[i].S;
                ll P=tree[t].S[i].F;
                cost+=tree[P].S[i].S;
                P=tree[P].S[i].F;
                tree[t].S.push_back({P,cost});
                if(P!=root){j=true;}
            }
        }
        High=tree[root].S.size();
    }
    
    //parent,cost
    pll search_parent(ll a,ll h){
        if(tree[a].F<=h){return {root,tree[a].S[High-1].S};}
        ll cost=0;
        for(ll i=High-1;i>=0;i--){
            if((1<<i)&h){
                cost+=tree[a].S[i].S;
                a=tree[a].S[i].F;
            }
        }
        return {a,cost};
    }
    
    //parent,a_cost_b_cost
    pair<ll,pll> search_lca(ll a,ll b){
        ll dif=tree[a].F-tree[b].F;
        ll a_cost=0;
        ll b_cost=0;
        if(0>dif){
            pll k=search_parent(b,-1*dif);
            b=k.F;
            b_cost+=k.S;
        }
        else{
            pll k=search_parent(a,dif);
            a=k.F;
            a_cost+=k.S;
        }
        for(ll i=High-1;i>=0;i--){
            if(tree[a].S[i].F!=tree[b].S[i].F){
                a_cost+=tree[a].S[i].S;
                a=tree[a].S[i].F;
                b_cost+=tree[b].S[i].S;
                b=tree[b].S[i].F;
            }
        }
        while(a!=b){
            a_cost+=tree[a].S[0].S;
            a=tree[a].S[0].F;
            b_cost+=tree[b].S[0].S;
            b=tree[b].S[0].F;
        }
        return {a,{a_cost,b_cost}};
    }
    
    
    ll high(ll a){
        return tree[a].F;
    }
};

ll cost(pair<ll,pll> P){
    return P.S.F+P.S.S;
}



int main(){
    ll n;
    cin>>n;
    weight_LCA lca(n,0);
    for(int i=0;i<n-1;i++){
        ll s,t,w;
        cin>>s>>t>>w;
        lca.add_edge(s,t,w);
        lca.add_edge(t,s,w);
    }
    lca.mk_tree();
    ll A=0;
    ll mx=0;
    for(int i=1;i<n;i++){
        ll c=cost(lca.search_lca(0,i));
        if(c>mx){mx=c; A=i;}
    }
    ll B=A;
    mx=0;
    for(int i=0;i<n;i++){
        ll c=cost(lca.search_lca(A,i));
        if(c>mx){mx=c; B=i;}
    }
    for(int i=0;i<n;i++){
        cout<<max(cost(lca.search_lca(A,i)),cost(lca.search_lca(B,i)))<<endl;
    }
    
    
    return 0;
}


```