시간 제한메모리 제한제출정답맞은 사람정답 비율
4 초 1024 MB31121254.545%

문제

당신은 성공적으로 여행사를 운영 중인 CEO다. 새로운 나라에서 여행사를 전개하고자 하는데 이를 위해서 첫 거점 도시를 정해야 한다.

새로운 나라는 $N$개의 도시가 존재하고 각 도시 간에 양방향으로 통행 가능한 $N-1$개의 도로가 존재한다. 어떠한 도시에서 출발해도 도로를 따라 다른 도시로 도착하는 것이 가능하다.

도시는 각각 해당 도시의 즐거움을 나타내는 수 $c_i$가 있다. 이 수가 클수록 즐거운 도시다.

여행사의 주력상품은 패키지 관광 상품이다. 패키지 관광은 거점 도시에서 출발하여 여러 도시를 지나는 관광 상품이다. 

패키지의 즐거움은 들른 도시 중에서 가장 큰 즐거움을 가진 도시의 즐거움과 가장 작은 즐거움을 가진 도시의 즐거움의 차이다.

재밌는 도시는 몇 번을 들러도 재밌고 재미없는 도시는 몇 번을 들러도 재미없기 때문에 패키지 도중에 한 도시를 여러번 들러도 괜찮다. 

이 나라에는 이상한 제한이 있는데 $i$번 도시에서 출발하는 관광버스는 $i$번 도시에서만 탑승할 수 있으며 최대 $d_i$만큼만 이동할 수 있다.

이러한 제한 때문에 패키지 설계에 골머리를 앓고 있는 당신은 꼼수를 하나 생각했다. 

$i$번 도시에서 출발하는 관광버스는 해당 도시에 있기만 하면 언제든지 탈 수 있기 때문에 거점으로 삼은 도시에서 출발하는 관광버스에 손님을 태우고 다른 도시로 가서 그 도시의 관광 버스에 손님들을 태우면 더 멀리 갈 수 있는 것이다.

이렇게 버스를 계속 갈아타는 것을 여러번 반복하면 훨씬 더 많은 도시에 갈 수 있다. 

여행사에서 최대한 즐거운 패키지 상품을 만드는 것은 중요하기 때문에 어떤 도시를 첫 거점으로 삼을지 다시 고민에 빠졌다.

도시와 도로의 정보가 주어졌을 때 모든 도시에 대해 각 도시를 거점도시로 지정했을 때 만들 수 있는 패키지 관광 상품의 최대 즐거움을 구하는 프로그램을 작성하자.

입력

첫 번째 줄에는 도시의 수 $N$이 주어진다. ($1 \le N \le 8\,000$)

두 번째 줄에는 $i$번째 도시의 즐거움 $c_i$가 공백으로 구분되어 $N$개 주어진다. ($0 \le c_i \le 10^{18}$)

세 번째 줄에는 $i$번째 도시에서 출발한 관광버스가 갈 수 있는 거리 $d_i$가 공백으로 구분되어 $N$개 주어진다. ($0 \le d_i \le 10^{18}$) 

네 번째 줄부터 $N-1$줄에 걸쳐 $i$번째 도로의 정보 $u_i$, $v_i$, $w_i$가 공백으로 구분되어 주어진다.

도시 $u_i$와 도시 $v_i$를 잇는 도로의 길이가 $w_i$라는 뜻이다. ($1 \le u_i, v_i \le N$, $u_i \neq v_i$, $1 \le w_i \le 10^9$)

주어지는 모든 수는 정수이다.

출력

$i$번째 줄에는 $i$번 도시에서 출발하는 패키지 상품 중에서 가장 큰 즐거움을 가지는 패키지의 즐거움을 총 $N$줄에 걸쳐 출력한다.

예제 입력 1

5
100 200 0 50 250
8 52 100 116 23
1 5 55
2 5 45
3 4 11
1 4 15

예제 출력 1

0
50
250
250
0

1번 도시에서 출발한 버스는 다른 도시에 도착하는 것이 불가능하다.

2번 도시에서 출발한 버스는 5번 도시에 도착이 가능하고 5번 도시에서 출발한 버스는 도착 가능한 도시가 없다. 

3번 도시에서 출발한 버스는 4번 도시에 도착이 가능하고 여기서 4번 도시에서 출발하는 버스로 갈아타면 모든 도시에 도착이 가능하다. 

4번 도시에서 출발한 버스는 모든 도시에 도착이 가능하다.

5번 도시에서 출발한 버스는 다른 도시에 도착하는 것이 불가능하다.

예제 입력 2

7
10 20 30 40 50 0 70
1 2 3 4 5 6 7
1 2 2
1 3 3
2 4 4
2 5 5
3 6 6
3 7 7

예제 출력 2

0
10
20
30
40
30
60