당신은 좀비고등학교의 서바이벌 서커스라는 모드를 아는가?
명의 참가자가 한 번에 링 안으로 뛰어들어, 점프대와 갖가지 장애물이 가득한 코스를 달리며 결승점까지 살아남는 자가 다음 라운드로 진출하는 짜릿한 서바이벌 방식의 모드이다. 좀비고등학교의 대표적인 대규모 경쟁 콘텐츠로, 오랫동안 많은 유저들의 사랑을 받아왔다.
이러한 인기에 보답하고자, PD는 서바이벌 서커스를 완전히 새로운 형태로 개편하기로 했다!
이번 시즌의 무대는 번부터 번까지 번호가 매겨진 개의 발판과 이 발판들을 잇는 개의 이동 통로로 이루어져 있다. 모든 발판은 이동 통로로 연결되어 있다. 즉, 발판과 이동 통로가 트리 구조를 이룬다. 번 발판은 모든 참가자가 최종적으로 도착해야 하는 결승점이다.
새로운 서바이벌 서커스에는 특별한 규칙이 하나 추가되었다. 참가자는 번 발판에서 번 발판까지의 단순 경로에 있는 발판 중 번 발판을 제외한 발판으로만 이동할 수 있다. 이때 현재 발판과 이동 통로로 직접 연결되지 않은 발판으로도 이동할 수 있다.
번 발판에는 그 발판의 불안정한 정도를 나타내는 불안정 계수 가 주어진다.
번 발판에서 번 발판으로 한 번에 이동하는 데 걸리는 시간은 다음과 같다.
여기서 는 번 발판과 번 발판을 잇는 단순 경로에 포함된 이동 통로의 가중치 합이다.
좀비고를 너무나도 사랑하는 rumi348은 새롭게 개편된 서바이벌 서커스를 정복하기로 결심했다!
rumi348은 어느 발판에서 시작하더라도 이동할 발판을 적절히 선택하여 결승점인 번 발판에 도착하려 한다. 이때 걸리는 시간을 최소화하고 싶다.
각 발판에서 시작하여 번 발판에 도착하는 데 필요한 최소 시간을 구해보자!
첫 번째 줄에 발판의 개수 이 주어진다.
두 번째 줄에 불안정 계수 이 공백으로 구분되어 주어진다.
세 번째 줄부터 개의 줄에 걸쳐 각 줄에 이동 통로가 연결하는 두 발판의 번호 , 와 가중치 가 공백으로 구분되어 주어진다.
입력으로 주어지는 수는 모두 정수이다.
첫 번째 줄부터 개의 줄에 걸쳐 번째 줄에 번 발판에서 시작하여 번 발판에 도착하는 데 필요한 최소 시간을 출력한다.
