#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>

#define rep(i,n) for(int i = 0; i < n; ++i)
#define X first
#define Y second
#define all(x) x.begin(), x.end()
using namespace std;
using PII=pair<int,int>;

//g -> index, dist
vector<PII> g[200000];

// Tree
class Node{
  public:
    int value;
    int parent;
    Node(){value=0;};
    Node(int d){value=d;};
};

Node nodes[200000];
int used[20000];
int a, b, c, n;
int ans;
const int INF = 1000000000;

PII B1, B2;


// dist, index
PII dfs(int from, int to){
  PII mx(0,to);
//   cout << "index: " << to<< endl;
  rep(i, g[to].size()){
    if(from == g[to][i].X)continue;
    PII val = dfs(to, g[to][i].X);
    val.X += g[to][i].Y;
    if(mx.X <  val.X){
      mx = val;
    }
  }
  return mx;

//   cout << "mx.X " << mx.X << " " << mx.Y << endl;
//   cout << endl;
}

PII diameter(){
  B1 = dfs(-1,0);
  B2 = dfs(-1, B1.Y);
  return B2;
}

void dijkstra(int from, int to, vector<int>& d){
  vector<int> used;
  used.resize(n, 0);
  priority_queue<PII, vector<PII>, greater<PII> > pq;
  pq.push(PII(0, from));
  d[from] = 0;

  while(!pq.empty()){
    int current = pq.top().Y;
    int d_sum = pq.top().X;pq.pop();

    if(d[current] < d_sum)continue;
//     cout << "current " << current << endl;

    rep(i, g[current].size()){
      //g -> index, dist
      int next = g[current][i].X;
      int cost = g[current][i].Y;

      if( d[next] > cost + d[current]){
        d[next] = cost + d[current];
        pq.push(PII(d[next] ,next));
      }
    }
  }
//   cout << "end" << endl;
}


int main(void){

  cin >> n;

  rep(i,n-1){
    cin >> a >> b >> c;
    if(a>b) swap(a,b);
    g[a].push_back(PII(b,c));
    g[b].push_back(PII(a,c));

    nodes[b].parent = a;
    nodes[b].value = c;
  }
//   cout << "end for" << endl;

  diameter();
//   cout << "dia" << endl;
  vector<int> d1, d2;
  d1.resize(n, INF);
  d2.resize(n, INF);
  dijkstra(B1.Y, B2.Y, d1);
  dijkstra(B2.Y, B1.Y, d2);

  rep(i,n){
     cout << max(d1[i], d2[i]) << endl;
  }

//   PII r = dfs(-1, 0);
//   cout << r.X << " " << r.Y << endl;
//   cout << endl;
//   PII t = dfs(-1, r.Y);
//   cout << t.X << " " << t.Y << endl;
//   cout << t.X << endl;
  

  return 0;
}
### Prompt

Your challenge is to write 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<vector>
#include<queue>
#include<algorithm>

#define rep(i,n) for(int i = 0; i < n; ++i)
#define X first
#define Y second
#define all(x) x.begin(), x.end()
using namespace std;
using PII=pair<int,int>;

//g -> index, dist
vector<PII> g[200000];

// Tree
class Node{
  public:
    int value;
    int parent;
    Node(){value=0;};
    Node(int d){value=d;};
};

Node nodes[200000];
int used[20000];
int a, b, c, n;
int ans;
const int INF = 1000000000;

PII B1, B2;


// dist, index
PII dfs(int from, int to){
  PII mx(0,to);
//   cout << "index: " << to<< endl;
  rep(i, g[to].size()){
    if(from == g[to][i].X)continue;
    PII val = dfs(to, g[to][i].X);
    val.X += g[to][i].Y;
    if(mx.X <  val.X){
      mx = val;
    }
  }
  return mx;

//   cout << "mx.X " << mx.X << " " << mx.Y << endl;
//   cout << endl;
}

PII diameter(){
  B1 = dfs(-1,0);
  B2 = dfs(-1, B1.Y);
  return B2;
}

void dijkstra(int from, int to, vector<int>& d){
  vector<int> used;
  used.resize(n, 0);
  priority_queue<PII, vector<PII>, greater<PII> > pq;
  pq.push(PII(0, from));
  d[from] = 0;

  while(!pq.empty()){
    int current = pq.top().Y;
    int d_sum = pq.top().X;pq.pop();

    if(d[current] < d_sum)continue;
//     cout << "current " << current << endl;

    rep(i, g[current].size()){
      //g -> index, dist
      int next = g[current][i].X;
      int cost = g[current][i].Y;

      if( d[next] > cost + d[current]){
        d[next] = cost + d[current];
        pq.push(PII(d[next] ,next));
      }
    }
  }
//   cout << "end" << endl;
}


int main(void){

  cin >> n;

  rep(i,n-1){
    cin >> a >> b >> c;
    if(a>b) swap(a,b);
    g[a].push_back(PII(b,c));
    g[b].push_back(PII(a,c));

    nodes[b].parent = a;
    nodes[b].value = c;
  }
//   cout << "end for" << endl;

  diameter();
//   cout << "dia" << endl;
  vector<int> d1, d2;
  d1.resize(n, INF);
  d2.resize(n, INF);
  dijkstra(B1.Y, B2.Y, d1);
  dijkstra(B2.Y, B1.Y, d2);

  rep(i,n){
     cout << max(d1[i], d2[i]) << endl;
  }

//   PII r = dfs(-1, 0);
//   cout << r.X << " " << r.Y << endl;
//   cout << endl;
//   PII t = dfs(-1, r.Y);
//   cout << t.X << " " << t.Y << endl;
//   cout << t.X << endl;
  

  return 0;
}
```