| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 4 초 | 1024 MB | 60 | 42 | 38 | 73.077% |
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. As it turns out, fighting off sea monsters can be quite expensive. In search of his next big plunder, Perry has scouted out each of the $N$ islands and has determined that the $i$-th island contains a treasure chest with $v_i$ coins inside.
It remains for him to plan out his next journey. He decides that he will sail through some (possibly empty) path of sea routes starting at island $x$ and ending at island $y$. At the end of his journey, he will open the chest at island $y$ and collect his well-earned booty.
There is one small problem though: Perry doesn’t know what island he’s currently on! Thus, for every possible starting island $x,ドル he would like to know the maximum possible number of coins he can earn out of all journeys starting at island $x$. Can you help him compute these values? You may assume Perry has enough coins to traverse any path of sea routes he chooses; he only cares about the net profit of his next journey.
The first line of input contains two space-separated integers $N$ and $M$.
The second line of input contains $N$ space-separated integers $v_1, v_2, \dots , v_N$ (0ドル ≤ v_i ≤ 10^9$).
The next $M$ lines each contain three space-separated integers $a_i,ドル $b_i$ (1ドル ≤ a_i , b_i ≤ N$), and $c_i$ (0ドル ≤ c_i ≤ 10^9$).
It is guaranteed that there is at most one sea route between any pair of islands and each sea route connects two distinct islands.
Output $N$ lines, where the $x$-th line contains the maximum possible net profit (in coins) of any journey starting at island $x$.
| Subtask | Score | Bounds on $N$ | Bounds on $M$ | Additional constraints |
|---|---|---|---|---|
| 1 | 5 | 1ドル ≤ N ≤ 3,円 000$ | 0ドル ≤ M ≤ 3,円 000$ | None |
| 2 | 5 | 1ドル ≤ N ≤ 10^6$ | 0ドル ≤ M ≤ 10^6$ | For all $i,ドル either $c_i = 0$ or $c_i = 10^9$ |
| 3 | 7 | 1ドル ≤ N ≤ 10^6$ | 0ドル ≤ M ≤ 10^6$ | Exactly one path of sea routes between any pair of islands |
| 4 | 8 | 1ドル ≤ N ≤ 10^6$ | 0ドル ≤ M ≤ 10^6$ | None |
4 5 6 5 9 2 1 2 0 3 2 3 4 3 6 1 3 5 2 4 2
6 6 9 4
For the first and third islands, it is best to just stay and open the chest on the island itself.
For the second island, Perry can travel to the first island and open the chest there. This has a net profit of 6ドル - 0 = 6$ coins and is the best possible net profit.
For the fourth island, Perry can to travel to the second and then the third island and open the chest there. This has a net profit of 9ドル - 2 - 3 = 4$ coins and is the best possible net profit.