22961번 - 여행사 운영하기

당신은 성공적으로 여행사를 운영 중인 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$줄에 걸쳐 출력한다.