이렇게 전체를 수정할 때는 그냥 전체를 다시 적어주세요.

옛날 옛날에, 아름다운 몰다비아의 지역에 1부터 N까지 고유한 번호가 붙여진 N개의 중세 도시가 있었다. 번호 1이 붙여진 도시는 수도이다. 도시들은 N-1개의 양방향 도로로 연결되어 있으며, 각 도로는 킬로미터 단위의 길이를 가지고 있다.

도시를 두 번 거치지 않고 도시의 쌍을 순회하는 방법은 유일하다. (즉 도로의 그래프가 트리 형태이다)

도시가 공격당했을 때, 최대한 빠른 시간 내에 이 사실을 수도에 보고해야 한다. 각 도시에 살고 있는 전령들이 이 메시지를 전달한다. 각각의 전령에는 여정을 시작하기 위해 필요한 시간과 일정 속력(킬로미터 당 분 단위)이 있다.

도시에서 출발한 메시지는 수도까지 유일한 가장 짧은 경로를 통해서 전달된다. 처음에는 공격당한 도시의 전령이 메시지를 전달한다. 그 전령이 순회하는 다른 도시에서 전령은 두 가지 선택을 할 수 있다. 수도 방향의 다음 도시로 이동하거나, 그 도시의 전령에게 메시지를 남길 수 있다. 새로운 전령은 위와 같은 방식을 따른다. 종합해보면, 메시지는 수도까지 전달되는 동안 여러 전령을 거칠 수 있다.

이때, 각 도시에서 수도까지 메시지를 전하는데 걸리는 최소 시간을 구하여라.

입력

첫째 줄엔, 몰다비아의 도시의 개수 N이 주어진다.

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

그 아래에, 한 줄에 하나씩 N-1개의 정수 쌍이 주어진다. i번째 쌍인 S_i, V_i는 (i+1)번째 도시의 전령을 표현하는 수이다. S_i는 여정을 준비하는데 걸리는 시간, V_i는 1km를 가는데 걸리는 시간(분)이다. 수도에는 전령이 없다.

• 3 ≤ N ≤ 100,000
• 0 ≤ S_i ≤ 10⁹
• 1 ≤ V_i ≤ 10⁹
• 각 도로의 길이는 10,000을 넘지 않는다.

출력

표준 출력에는 N-1개의 정수로 이루어진 하나의 줄을 출력해야 한다. i번째 수는 (i+1)번째 도시에서 수도로 메시지를 보내는데 필요한 최소 시간(분)을 나타낸다.

수정했습니다.