시간 제한메모리 제한제출정답맞힌 사람정답 비율
4 초 1024 MB45201954.286%

문제

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

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

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

이 나라에는 이상한 제한이 있는데 $i$​번 도시에서 출발하는 관광버스는 ​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