You are given a tree consisting of n nodes and rooted at 1. Each node and each edge of the tree have a value associated with them. Consider a node j and one of it's ancestor node i. Cost of node j with respect to node i is defined as sum of value of node j and sum of value of all edges present in the simple path from node i to node j. For each node i, output the number of distinct costs of all its descendants.

Input Format
First line contains n denoting the number of tree nodes.
Next n-1 lines each contain 3 integer numbers \(a, b, c\) denoting an edge between node a and node b of value c.
Next line contains n integers denoting the value of each node.

Output Format
For node i ranging from 1 to n, output the number of distinct costs among its descendants, each on a new line.

Constraints
\(1\le n\le 10^5\)
\(-10^9\le Value Of Node,Value Of Edge\le 10^9\)