시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 31 5 5 35.714%

문제

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

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

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

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

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

입력

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

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

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

  • 3 ≤ N ≤ 100,000
  • 0 ≤ Si ≤ 109
  • 1 ≤ V≤ 109
  • 각 도로의 길이는 10,000을 넘지 않는다.

출력

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

예제 입력

5
1 2 20
2 3 12
2 4 1
4 5 3
26 9
1 10
500 2
2 30

예제 출력

206 321 542 328

힌트