KOI국은 N개의 도시들이 M개의 기차 노선을 통해 연결된 그래프로 표현할 수 있다.

i번째 도로는 연결하는 두 도시 Ui와 Vi, 그리고 그 철도 폭 Wi로 표현된다.

당연하게도, 철도 폭이 도로마다 다르면 열차가 운행할 수 없다.

그래서 도시 간 이동할 때 KOI국의 국민들은 열차 여려 대를 환승했어야 했다.

이런 불편함을 없애기 위해 KOI국의 왕 재민이는 철도 폭을 수정하는 공사를 펼치려 한다.

각 공사는 여러 개의 노선에서 진행할 텐데, 어느 철도 노선 하나의 폭을 1 늘리거나 1 줄일 때마다 1 만큼의 비용이 든다.

재민이는 철도 폭 Xi에 대해, 모든 도시 쌍 사이를 폭이 Xi인 열차 한 대로 운행할 수 있도록 최소의 비용으로 공사를 진행하고자 한다.

총 Q개의 철도 폭에 대해 최적의 공사 비용을 각각 출력하시오.

도로 공사 timer 5s memory 1024MB

도로 공사 5s 1024MB