Treasure Hunt

Perry the Pirate is sailing the seven seas! He has a map consisting of $N$ islands connected by a network of $M$ sea routes. The $i$-th sea route connects islands $a_i$ and $b_i$ and costs $c_i$ coins to traverse in either direction. Fighting off sea monsters is expensive. Perry has scouted each of the $N$ islands and found that the $i$-th island has a treasure chest with $v_i$ coins inside.

Next, he plans his journey. He sails along some (possibly empty) path of sea routes that starts at island $x$ and ends at island $y$. At the end, he opens the chest at island $y$ and collects the booty.

There is one problem. Perry does not know which island he is on. For every possible starting island $x$, he wants the maximum number of coins he can earn over all journeys starting at island $x$. You may assume Perry has enough coins to traverse any path he chooses. He only cares about the net profit of the journey.

The first line contains two space-separated integers $N$ and $M$.

The second line contains $N$ space-separated integers $v_1, v_2, \ldots, v_N$ ($0 \le v_i \le 10^9$).

The next $M$ lines each contain three space-separated integers $a_i$, $b_i$ ($1 \le a_i, b_i \le N$), and $c_i$ ($0 \le c_i \le 10^9$). There is at most one sea route between any pair of islands, and each sea route connects two distinct islands.

Output $N$ lines. The $x$-th line contains the maximum net profit (in coins) of any journey starting at island $x$.