정올국은 N개의 섬으로 이루어져 있고 그중 K개의 섬에서 세관신고를 할 수 있다. 행정상 편의를 위해 섬들의 코드를 1~N으로 매겨놓고, 세관신고가 가능한 섬들의 코드는 1~K로 지정해 놓았다.

정올국의 N개의 섬에는 공항이 있어서 비행기를 타고 다른 섬으로 갈 수 있다. 정올국의 해양기후가 매우 안 좋기 때문에 오직 비행기로만 섬 사이를 이동할 수 있다.

정올국에는 총 M개의 여행사가 있고 각 여행사는 Pi의 요금을 내고 Di번 섬에서 Ai번 섬으로 가는 편도 여행을 제공한다.

주찬이는 여행을 계획하는 Q명의 사람들에 대해서 S번 섬에서 E번 섬으로 가는 데 드는 최소비용을 구해야 한다. 같은 섬을 여러 번 들러도 되지만, 생태계를 보호하고 테러를 방지하기 위해 여행 도중에 세관신고를 반드시 해야 한다. 이러다 보니, S번 섬에서 E번 섬으로 가는 것이 아예 불가능할 수도 있다.

모든 여행의 요청을 받으면, 그중 가능한 경로의 수와 최소비용의 합을 구하는 프로그램을 작성하여라.

#1517 upload 29 done 7 how_to_reg 7

여행 timer 1s memory 64MB

#1517

여행 1s 64MB