#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

template <class T>
using lp_queue=priority_queue<T, deque<T>, greater<T>>;

using Weight=long long;
static const Weight INF=1LL<<57;

struct Edge {
    size_t src, dst;
    Weight weight;
    Edge() {}
    Edge(size_t src, size_t dst, Weight weight=1):
        src(src), dst(dst), weight(weight)
    {}
};

bool operator<(const Edge &e, const Edge &f) {
    if (e.weight != f.weight) {
        return e.weight > f.weight;
    } else {
        return e.src!=f.src? e.src<f.src : e.dst<f.dst;
    }
}

using Edges=vector<Edge>;
using Vertex=vector<Edge>;
using Graph=vector<Vertex>;

void join(Graph &g, size_t s, size_t d, Weight w=1) {
    // non-directed
    g[s].push_back(Edge(s, d, w));
    g[d].push_back(Edge(d, s, w));
}

void connect(Graph &g, size_t s, size_t d, Weight w=1) {
    // directed
    g[s].push_back(Edge(s, d, w));
}

Weight visit(const Graph &g, Graph &h, size_t i, size_t j) {
    if (h[i][j].weight >= 0) return h[i][j].weight;

    h[i][j].weight = g[i][j].weight;
    size_t u=h[i][j].dst;
    for (size_t k=0; k<h[u].size(); ++k) {
        if (h[u][k].dst == i) continue;
        h[i][j].weight = max(h[i][j].weight, visit(g, h, u, k)+g[i][j].weight);
    }

    return h[i][j].weight;
}

vector<Weight> get_treeheight(const Graph &g) {
    size_t V=g.size();
    Graph h(g);
    for (size_t i=0; i<V; ++i)
        for (Edge &e: h[i])
            e.weight = -INF;

    for (size_t i=0; i<V; ++i)
        for (size_t j=0; j<h[i].size(); ++j)
            if (h[i][j].weight < 0)
                h[i][j].weight = visit(g, h, i, j);

    vector<Weight> height(V);
    for (size_t i=0; i<V; ++i)
        for (Edge &e: h[i])
            height[i] = max(height[i], e.weight);

    return height;
}

int main() {
    size_t V, E;
    scanf("%zu", &V);
    E = V-1;

    Graph g(V);
    for (size_t i=0; i<E; ++i) {
        size_t s, t, w;
        scanf("%zu %zu %lld", &s, &t, &w);

        join(g, s, t, w);
    }

    vector<Weight> height=get_treeheight(g);

    for (Weight w: height)
        printf("%lld\n", w);

    return 0;
}
### Prompt

Construct a Cpp code solution to the problem outlined:

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 <cstdio>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

template <class T>
using lp_queue=priority_queue<T, deque<T>, greater<T>>;

using Weight=long long;
static const Weight INF=1LL<<57;

struct Edge {
    size_t src, dst;
    Weight weight;
    Edge() {}
    Edge(size_t src, size_t dst, Weight weight=1):
        src(src), dst(dst), weight(weight)
    {}
};

bool operator<(const Edge &e, const Edge &f) {
    if (e.weight != f.weight) {
        return e.weight > f.weight;
    } else {
        return e.src!=f.src? e.src<f.src : e.dst<f.dst;
    }
}

using Edges=vector<Edge>;
using Vertex=vector<Edge>;
using Graph=vector<Vertex>;

void join(Graph &g, size_t s, size_t d, Weight w=1) {
    // non-directed
    g[s].push_back(Edge(s, d, w));
    g[d].push_back(Edge(d, s, w));
}

void connect(Graph &g, size_t s, size_t d, Weight w=1) {
    // directed
    g[s].push_back(Edge(s, d, w));
}

Weight visit(const Graph &g, Graph &h, size_t i, size_t j) {
    if (h[i][j].weight >= 0) return h[i][j].weight;

    h[i][j].weight = g[i][j].weight;
    size_t u=h[i][j].dst;
    for (size_t k=0; k<h[u].size(); ++k) {
        if (h[u][k].dst == i) continue;
        h[i][j].weight = max(h[i][j].weight, visit(g, h, u, k)+g[i][j].weight);
    }

    return h[i][j].weight;
}

vector<Weight> get_treeheight(const Graph &g) {
    size_t V=g.size();
    Graph h(g);
    for (size_t i=0; i<V; ++i)
        for (Edge &e: h[i])
            e.weight = -INF;

    for (size_t i=0; i<V; ++i)
        for (size_t j=0; j<h[i].size(); ++j)
            if (h[i][j].weight < 0)
                h[i][j].weight = visit(g, h, i, j);

    vector<Weight> height(V);
    for (size_t i=0; i<V; ++i)
        for (Edge &e: h[i])
            height[i] = max(height[i], e.weight);

    return height;
}

int main() {
    size_t V, E;
    scanf("%zu", &V);
    E = V-1;

    Graph g(V);
    for (size_t i=0; i<E; ++i) {
        size_t s, t, w;
        scanf("%zu %zu %lld", &s, &t, &w);

        join(g, s, t, w);
    }

    vector<Weight> height=get_treeheight(g);

    for (Weight w: height)
        printf("%lld\n", w);

    return 0;
}
```