여행사 운영하기

당신은 성공적으로 여행사를 운영하는 CEO다. 새로운 나라에서 여행사를 확장하려고 하며, 이를 위해 첫 거점 도시를 정해야 한다.

이 나라에는 $N$개의 도시가 있고, 도시 사이를 양방향으로 오갈 수 있는 $N-1$개의 도로가 있다. 어느 도시에서 출발하든 도로를 따라 다른 모든 도시에 도착할 수 있다.

각 도시 $i$에는 즐거움을 나타내는 수 $c_i$가 있다. 이 값이 클수록 즐거운 도시다.

이 나라에는 특이한 제한이 있다. $i$번 도시에서 출발하는 관광버스는 $i$번 도시에서만 탈 수 있고, $i$번 도시로부터 거리가 $d_i$ 이하인 도시로만 이동할 수 있다.

$i$번 도시의 관광버스는 그 도시에 있기만 하면 언제든지 탈 수 있다. 따라서 거점 도시에서 출발한 버스에 손님을 태워 다른 도시로 간 뒤, 그 도시의 관광버스로 갈아타면 더 멀리 갈 수 있다. 이렇게 버스를 여러 번 갈아타면 거점 도시의 버스만 이용할 때보다 훨씬 많은 도시에 갈 수 있다.

거점 도시를 정할 때 중요한 것은, 거점 도시에서 도달할 수 있는 도시들의 즐거움 최댓값과 최솟값의 차이다.

도시와 도로 정보가 주어졌을 때, 각 도시를 거점 도시로 정했을 때 도달할 수 있는 도시들의 즐거움 최댓값과 최솟값의 차이를 구하라.

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

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

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

네 번째 줄부터 $N-1$개의 줄에 걸쳐 도로 정보 $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$줄을 출력한다.