전령들

아름다운 몰다비아 지방에는 $1$번부터 $N$번까지 서로 다른 번호가 붙은 $N$개의 중세 도시가 있다. $1$번 도시는 수도이다. 도시들은 $N-1$개의 양방향 도로로 연결되어 있으며, 각 도로에는 킬로미터 단위의 길이가 있다. 어떤 두 도시 사이에도 같은 도시를 두 번 지나지 않고 이동하는 경로가 정확히 하나 존재한다. 즉, 도로들이 이루는 그래프는 트리이다.

도시가 공격을 받으면 이 사실을 최대한 빨리 수도에 알려야 한다. 수도를 제외한 각 도시에는 전령이 한 명씩 살고 있으며, 전령마다 출발을 준비하는 데 걸리는 시간과 $1$킬로미터를 이동하는 데 걸리는 시간(분)이 정해져 있다.

메시지는 공격받은 도시에서 수도까지 이어지는 유일한 경로를 따라 전달된다. 처음에는 공격받은 도시의 전령이 메시지를 든다. 전령은 경로 위의 도시에 도착할 때마다 다음 두 가지 중 하나를 선택할 수 있다. 수도 쪽으로 한 도시 더 이동하거나, 그 도시에 사는 전령에게 메시지를 넘길 수 있다. 메시지를 넘겨받은 전령도 똑같은 방식으로 행동한다. 따라서 메시지는 수도에 도착하기까지 여러 전령의 손을 거칠 수 있다. 전령이 메시지를 들 때마다 그 전령의 준비 시간이 새로 필요하다.

각 도시에서 출발한 메시지가 수도에 도착하기까지 걸리는 최소 시간(분)을 구하여라.

첫째 줄에 도시의 개수 $N$이 주어진다.

다음 $N-1$개의 줄에는 각각 공백으로 구분된 세 정수 $U$, $V$, $D$가 주어진다. 이는 도시 $U$와 도시 $V$가 길이 $D$킬로미터의 도로로 연결되어 있음을 뜻한다.

그 다음 $N-1$개의 줄에는 각각 두 정수 $S_i$, $V_i$가 주어진다. $i$번째 줄은 $(i+1)$번 도시에 사는 전령을 나타내며, $S_i$는 출발을 준비하는 데 걸리는 시간, $V_i$는 $1$킬로미터를 이동하는 데 걸리는 시간(분)이다. 수도($1$번 도시)에는 전령이 없다.

한 줄에 $N-1$개의 정수를 공백으로 구분하여 출력한다. $i$번째 수는 $(i+1)$번 도시에서 출발한 메시지가 수도에 도착하기까지 걸리는 최소 시간(분)이다.

• $3 \le N \le 100000$
• $0 \le S_i \le 10^9$
• $1 \le V_i \le 10^9$
• $1 \le D \le 10000$