#include <bits/stdc++.h>
#define REP(i,n) for (long i=0;i<(n);i++)
#define FOR(i,a,b) for (long i=(a);i<(b);i++)
#define RREP(i,n) for(long i=n;i>=0;i--)
#define RFOR(i,a,b) for(long i=(a);i>(b);i--)
#define dump1d_arr(array) REP(i,array.size()) cerr << #array << "[" << (i) << "] ==> " << (array[i]) << endl;
#define dump2d_arr(array) REP(i,array.size()) REP(j,array[i].size()) cerr << #array << "[" << (i) << "]" << "[" << (j) << "] ==> " << (array[i][j]) << endl;
#define dump(x)  cerr << #x << " => " << (x) << endl;
#define dumpP(p) cerr << "( " << p.first << " , " << p.second << " )" << endl;
#define CLR(vec) { REP(i,vec.size()) vec[i] = 0; } 
#define SORT(c) sort((c).begin(),(c).end())
#define MIN(vec) *min_element(vec.begin(), vec.end());
#define MAX(vec) *max_element(vec.begin(), vec.end());
#define UNIQ(vec) vec.erase(unique(vec.begin(), vec.end()),vec.end());
#define IN(n,m)  (!(m.find(n) == m.end()))
#define TO_INT(vec,s) REP(i,s.length()){vec.push_back(s[i] - ‘0’);}
#define ENUM_v(vec) for (auto e : vec)
#define dump_MAP(m) for(auto itr = m.begin(); itr != m.end(); ++itr) { cerr << itr->first << " --> "  << itr->second << endl; }
#define FINDL(vec,x) (lower_bound(vec.begin(),vec.end(),x) - vec.begin())
#define FINDU(vec,x) (upper_bound(vec.begin(),vec.end(),x) - vec.begin())
#define ROUND(N) setprecision(N)
using namespace std;
constexpr long mod = 1000000007;
constexpr short shINF = 32767;
constexpr long loINF = 2147483647;
constexpr long long llINF = 9223372036854775807;
typedef long long LL;
typedef vector<long> VI;
typedef vector<VI> VVI;

template <typename T,typename D>
class Tree {
private:
	typedef struct {T node;D dist;T prev;} P;
	typedef pair<T,D> pr;
	typedef vector<pr> VP;
	vector<VP> E;
	T V;
public:
	Tree() : V(0){}
	Tree(T v) : V(v),E(v) {}

	void addEdgeDirected(T start,T goal,D weight){
		E[start].push_back(pr(goal,weight));
	}

	void addEdgeUndirected(T start,T goal,D weight){
		E[start].push_back(pr(goal,weight));
		E[goal].push_back(pr(start,weight));
	}

	pair<T,D> farthest(T node){ // nodeからの最遠点(頂点,距離)
		vector<T> Dis;
		calcDist(node,Dis);
		T ret = (-1),dist = (-1);
		REP(i,V) {
			if (dist < Dis[i]) {
				ret = i;
            	dist = Dis[i];
			}
		}
		return (pair<T,D>(ret,dist));
	}

	void calcDist(T v, vector<D>& Dis) {
    	Dis.clear(); Dis.resize(V,loINF);
    	Dis[v] = 0;
    	queue<T> Q;
    	Q.push(v);
    	while (!Q.empty()) {
        	T c = Q.front(); Q.pop();
        	REP(i,E[c].size()) {
            	if (Dis[E[c][i].first] > Dis[c] + E[c][i].second) {
                	Dis[E[c][i].first] = Dis[c] + E[c][i].second;
                	Q.push(E[c][i].first);
            	}
            }
        }
    }

	vector<T> getHeight(void) { //全部のnodeの最遠距離。
		vector<T> Dis(V);
		T x = farthest(0).first;
   		T y = farthest(x).first;
    	vector<T> DX; calcDist(x, DX);
    	vector<T> DY; calcDist(y, DY);
    	REP(i,V) Dis[i] = max(DX[i],DY[i]);
    	return Dis;
	}

	pair<T,D> getDiameter(void){
		stack<P> st;
		pair<T,D> farV(V-1,0);
		st.push(P {V-1,0,-1});
		while (!st.empty()) {
			P e = st.top();
			st.pop();
			if (farV.second < e.dist) farV = pair<T,D> (e.node,e.dist);
			for ( auto &p : E[e.node]) {
				if (p.first != e.prev) st.push(P {p.first,e.dist+p.second,e.node});
			}
		}
		pair<T,D> farV2(farV.first,0);
		st.push(P {farV.first,0,-1});
		while (!st.empty()) {
			P e = st.top();
			st.pop();
			if (farV2.second < e.dist) farV2 = pair<T,D> (e.node,e.dist);
			for ( auto &p : E[e.node]) {
				if (p.first != e.prev) st.push(P {p.first,e.dist+p.second,e.node});
			}
		}
		return farV2;
	}
};

int main(void) {
	long N,s,t,w;
	cin >> N;
	Tree<long,long> tr(N);
	REP(i,N-1){
		cin >> s >> t >> w;
		tr.addEdgeUndirected(s,t,w);
	}
	vector<long> p = tr.getHeight();
	REP(i,N) cout << p[i] << endl;
}

### Prompt

Please create a solution in CPP to the following problem:

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 <bits/stdc++.h>
#define REP(i,n) for (long i=0;i<(n);i++)
#define FOR(i,a,b) for (long i=(a);i<(b);i++)
#define RREP(i,n) for(long i=n;i>=0;i--)
#define RFOR(i,a,b) for(long i=(a);i>(b);i--)
#define dump1d_arr(array) REP(i,array.size()) cerr << #array << "[" << (i) << "] ==> " << (array[i]) << endl;
#define dump2d_arr(array) REP(i,array.size()) REP(j,array[i].size()) cerr << #array << "[" << (i) << "]" << "[" << (j) << "] ==> " << (array[i][j]) << endl;
#define dump(x)  cerr << #x << " => " << (x) << endl;
#define dumpP(p) cerr << "( " << p.first << " , " << p.second << " )" << endl;
#define CLR(vec) { REP(i,vec.size()) vec[i] = 0; } 
#define SORT(c) sort((c).begin(),(c).end())
#define MIN(vec) *min_element(vec.begin(), vec.end());
#define MAX(vec) *max_element(vec.begin(), vec.end());
#define UNIQ(vec) vec.erase(unique(vec.begin(), vec.end()),vec.end());
#define IN(n,m)  (!(m.find(n) == m.end()))
#define TO_INT(vec,s) REP(i,s.length()){vec.push_back(s[i] - ‘0’);}
#define ENUM_v(vec) for (auto e : vec)
#define dump_MAP(m) for(auto itr = m.begin(); itr != m.end(); ++itr) { cerr << itr->first << " --> "  << itr->second << endl; }
#define FINDL(vec,x) (lower_bound(vec.begin(),vec.end(),x) - vec.begin())
#define FINDU(vec,x) (upper_bound(vec.begin(),vec.end(),x) - vec.begin())
#define ROUND(N) setprecision(N)
using namespace std;
constexpr long mod = 1000000007;
constexpr short shINF = 32767;
constexpr long loINF = 2147483647;
constexpr long long llINF = 9223372036854775807;
typedef long long LL;
typedef vector<long> VI;
typedef vector<VI> VVI;

template <typename T,typename D>
class Tree {
private:
	typedef struct {T node;D dist;T prev;} P;
	typedef pair<T,D> pr;
	typedef vector<pr> VP;
	vector<VP> E;
	T V;
public:
	Tree() : V(0){}
	Tree(T v) : V(v),E(v) {}

	void addEdgeDirected(T start,T goal,D weight){
		E[start].push_back(pr(goal,weight));
	}

	void addEdgeUndirected(T start,T goal,D weight){
		E[start].push_back(pr(goal,weight));
		E[goal].push_back(pr(start,weight));
	}

	pair<T,D> farthest(T node){ // nodeからの最遠点(頂点,距離)
		vector<T> Dis;
		calcDist(node,Dis);
		T ret = (-1),dist = (-1);
		REP(i,V) {
			if (dist < Dis[i]) {
				ret = i;
            	dist = Dis[i];
			}
		}
		return (pair<T,D>(ret,dist));
	}

	void calcDist(T v, vector<D>& Dis) {
    	Dis.clear(); Dis.resize(V,loINF);
    	Dis[v] = 0;
    	queue<T> Q;
    	Q.push(v);
    	while (!Q.empty()) {
        	T c = Q.front(); Q.pop();
        	REP(i,E[c].size()) {
            	if (Dis[E[c][i].first] > Dis[c] + E[c][i].second) {
                	Dis[E[c][i].first] = Dis[c] + E[c][i].second;
                	Q.push(E[c][i].first);
            	}
            }
        }
    }

	vector<T> getHeight(void) { //全部のnodeの最遠距離。
		vector<T> Dis(V);
		T x = farthest(0).first;
   		T y = farthest(x).first;
    	vector<T> DX; calcDist(x, DX);
    	vector<T> DY; calcDist(y, DY);
    	REP(i,V) Dis[i] = max(DX[i],DY[i]);
    	return Dis;
	}

	pair<T,D> getDiameter(void){
		stack<P> st;
		pair<T,D> farV(V-1,0);
		st.push(P {V-1,0,-1});
		while (!st.empty()) {
			P e = st.top();
			st.pop();
			if (farV.second < e.dist) farV = pair<T,D> (e.node,e.dist);
			for ( auto &p : E[e.node]) {
				if (p.first != e.prev) st.push(P {p.first,e.dist+p.second,e.node});
			}
		}
		pair<T,D> farV2(farV.first,0);
		st.push(P {farV.first,0,-1});
		while (!st.empty()) {
			P e = st.top();
			st.pop();
			if (farV2.second < e.dist) farV2 = pair<T,D> (e.node,e.dist);
			for ( auto &p : E[e.node]) {
				if (p.first != e.prev) st.push(P {p.first,e.dist+p.second,e.node});
			}
		}
		return farV2;
	}
};

int main(void) {
	long N,s,t,w;
	cin >> N;
	Tree<long,long> tr(N);
	REP(i,N-1){
		cin >> s >> t >> w;
		tr.addEdgeUndirected(s,t,w);
	}
	vector<long> p = tr.getHeight();
	REP(i,N) cout << p[i] << endl;
}

```