#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<list>
#include<string>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<ctime>
using namespace std;

typedef long long ll;

bool debug = false;
const int NIL = -1;
const int INF = 1000000000;
const int NUM = 100010;
clock_t START, END;

int V;

struct HeapNode {
	int d, u;
	bool operator < (const HeapNode& rhs) const {
		return d > rhs.d;
	}
};

struct Edge {
	int from, to, dist;
	Edge(int u, int v, int d) :from(u), to(v), dist(d) {}
};

struct Dijkstra {
	int n, m;
	vector<Edge> edges;
	vector<int> G[NUM];
	
	int up[NUM], down_1[NUM], child[NUM], down_2[NUM];

	void init(int n) {
		this->n = n;
		for (int i = 0; i < n; i++)
			G[i].clear();
		edges.clear();
	}

	void AddEdge(int from, int to, int dist) {
		edges.push_back(Edge(from, to, dist));
		m = edges.size();
		G[from].push_back(m - 1);
	}

	void dfs1(int u, int fa) {
		down_1[u] = down_2[u] = 0;
		for (int i = 0; i < G[u].size(); i++) {
			int v = edges[G[u][i]].to;
			if (v != fa) {
				dfs1(v, u);
				if (down_1[v] + edges[G[u][i]].dist > down_1[u]) {
					down_2[u] = down_1[u];
					down_1[u] = down_1[v] + edges[G[u][i]].dist;
					child[u] = v;
				}
				else if (down_1[v] + edges[G[u][i]].dist > down_2[u])
					down_2[u] = down_1[v] + edges[G[u][i]].dist;
			}
		}
	}

	void dfs2(int u, int fa) {
		for (int i = 0; i < G[u].size(); i++) {
			int v = edges[G[u][i]].to;
			if (v == fa)
				continue;
			if (child[u] != v)
				up[v] = max(up[u] + edges[G[u][i]].dist, down_1[u] + edges[G[u][i]].dist);
			else
				up[v] = max(up[u] + edges[G[u][i]].dist, down_2[u] + edges[G[u][i]].dist);
			dfs2(v, u);
		}
	}
};

Dijkstra solve;

int main(void)
{
	if (debug) {
		START = clock();
		freopen("in29.txt", "r", stdin);
		freopen("out.txt", "w", stdout);
	}
	int s, t, d;
	cin >> V;
	solve.init(V);
	for (int i = 0; i < V - 1; i++) {
		scanf("%d%d%d", &s, &t, &d);
		solve.AddEdge(s, t, d);
		solve.AddEdge(t, s, d);
	}
	solve.dfs1(0, -1);
	solve.dfs2(0, -1);
	for (int i = 0; i < V; i++)
		cout << max(solve.up[i], solve.down_1[i]) << endl;
	if (debug) {
		END = clock();
		double endtime = (double)(END - START) / 1000;
		printf("total time = %lf s", endtime);
	}
	return 0;
}

### Prompt

Your task is to create a Cpp solution 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<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<list>
#include<string>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<ctime>
using namespace std;

typedef long long ll;

bool debug = false;
const int NIL = -1;
const int INF = 1000000000;
const int NUM = 100010;
clock_t START, END;

int V;

struct HeapNode {
	int d, u;
	bool operator < (const HeapNode& rhs) const {
		return d > rhs.d;
	}
};

struct Edge {
	int from, to, dist;
	Edge(int u, int v, int d) :from(u), to(v), dist(d) {}
};

struct Dijkstra {
	int n, m;
	vector<Edge> edges;
	vector<int> G[NUM];
	
	int up[NUM], down_1[NUM], child[NUM], down_2[NUM];

	void init(int n) {
		this->n = n;
		for (int i = 0; i < n; i++)
			G[i].clear();
		edges.clear();
	}

	void AddEdge(int from, int to, int dist) {
		edges.push_back(Edge(from, to, dist));
		m = edges.size();
		G[from].push_back(m - 1);
	}

	void dfs1(int u, int fa) {
		down_1[u] = down_2[u] = 0;
		for (int i = 0; i < G[u].size(); i++) {
			int v = edges[G[u][i]].to;
			if (v != fa) {
				dfs1(v, u);
				if (down_1[v] + edges[G[u][i]].dist > down_1[u]) {
					down_2[u] = down_1[u];
					down_1[u] = down_1[v] + edges[G[u][i]].dist;
					child[u] = v;
				}
				else if (down_1[v] + edges[G[u][i]].dist > down_2[u])
					down_2[u] = down_1[v] + edges[G[u][i]].dist;
			}
		}
	}

	void dfs2(int u, int fa) {
		for (int i = 0; i < G[u].size(); i++) {
			int v = edges[G[u][i]].to;
			if (v == fa)
				continue;
			if (child[u] != v)
				up[v] = max(up[u] + edges[G[u][i]].dist, down_1[u] + edges[G[u][i]].dist);
			else
				up[v] = max(up[u] + edges[G[u][i]].dist, down_2[u] + edges[G[u][i]].dist);
			dfs2(v, u);
		}
	}
};

Dijkstra solve;

int main(void)
{
	if (debug) {
		START = clock();
		freopen("in29.txt", "r", stdin);
		freopen("out.txt", "w", stdout);
	}
	int s, t, d;
	cin >> V;
	solve.init(V);
	for (int i = 0; i < V - 1; i++) {
		scanf("%d%d%d", &s, &t, &d);
		solve.AddEdge(s, t, d);
		solve.AddEdge(t, s, d);
	}
	solve.dfs1(0, -1);
	solve.dfs2(0, -1);
	for (int i = 0; i < V; i++)
		cout << max(solve.up[i], solve.down_1[i]) << endl;
	if (debug) {
		END = clock();
		double endtime = (double)(END - START) / 1000;
		printf("total time = %lf s", endtime);
	}
	return 0;
}

```