E. The Deadly Escape
time limit per test
1 second
memory limit per test
128 megabytes
input
standard input
output
standard output

In the Squid Game, players find themselves trapped in a massive, deadly tree-like structure with $$$n$$$ platforms (nodes). Each platform has a danger level $$$a_i$$$, representing its instability. Platforms are connected by rope bridges with different weight values $$$w_i$$$, determining the difficulty of crossing between them. Players can jump from one platform to any platform in its subtree, but each jump comes at a cost:

jump's cost $$$=a_y$$$ $$$($$$weight of the path from $$$x$$$ to $$$y$$$$$$)$$$

where $$$x$$$ is the current platform and $$$y$$$ is the destination.

The goal for each player, starting from any platform, is to find the safest escape route to a leaf platform, where the total jumping cost is minimized. However, the root platform (1) is cursed and can never be a leaf, even if it has only one connection!

Can you find the optimal escape path for each platform before the deadly Squid Game masters close in?

Input

The first line of input contains an integer $$$n$$$ ($$$2 \leq n \leq 10^5$$$), the number of nodes in the tree.

The second line contains $$$n$$$ space-separated integers $$$a_1, a_2, \dots, a_n$$$ ($$$-10^6 \leq a_i \leq 10^6$$$),representing each platform danger level.

Next $$$n - 1$$$ lines contain two space-separated integers $$$u_i$$$ , $$$v_i$$$ and $$$w_i$$$ ($$$1 \leq u_i, v_i \leq n , -10^6 \leq w_i \leq 10^6$$$) describing a rope bridge between platforms $$$u_i$$$ and $$$v_i$$$ given its weight.

Output

Output $$$n$$$ space-separated integers, the $$$i$$$-th of which denotes the minimum cost of a path from platform $$$i$$$ to reach any leaf.

Examples
Input
3
2 -1 1
1 2 3
2 3 -2
Output
-5 -2 0
Input
5
3 -1 2 -2 -4
1 2 3
1 3 -1
3 4 -2
3 5 1
Output
-6 0 -4 0 0
Input
7
1 -3 2 -4 5 -3 -1
1 2 -1
1 3 -2
2 4 2
2 5 -1
3 6 -2
3 7 1
Output
-10 -8 -1 0 0 0 0