재민이는 최근 배달 알바를 시작했다.

재민이는 오늘도 오토바이를 타고 도심을 질주하며 따끈한 음식을 배달하고 있다.

재민이가 일을 하는 정올동은 N개의 건물과 두 건물 사이를 양방향으로 잇는 M개의 도로가 있다.

i번째 도로는 A_i번 건물과 B_i번 건물 사이를 연결하며 재민이의 오토바이가 통과하는데 C_i의 시간이 걸린다.

재민이의 오토바이는 너무 빨라서 유턴을 할 수가 없다.

여기서 말하는 유턴이란, 건물 u에서 건물 v로 이동 했다가 곧바로 같은 도로를 통해 u로 돌아 나오는 것을 의미한다.

물론 도로 한가운데에서 방향을 바꾸는 것도 당연히 불가능하다.

재민이는 T일동안 L개의 주문을 배달한다.

0일째의 주문은 X_1, X_2, ... , X_L로 주어지며 해당하는 번호의 건물들에 순서대로 음식을 배달해야 한다는 의미이다.

이 L개의 주문은 단골손님들이 하는 것이라 거의 바뀌지 않는다.

하지만 앞으로의 T일간 하루에 하나씩의 주문 위치가 변경된다.

보다 구체적으로 k번째 날에는 X_{P_k}번 주문이 Q_k번 건물로 변경된다.

언제나 같은 건물로의 배달이 연속한 경우는 없으며 건물에 도달한 다음 배달에 걸리는 시간은 무시해도 좋다.

여러분이 할 일은 매일 주문이 변경될 때마다 재민이가 모든 음식을 순서대로 배달하는데 걸리는 최소 시간을 구하는 것이다.

어떤 날은 배달이 아예 불가능 할 수도 있음을 명심하라.

배달의 민족 timer 10s memory 1024MB

배달의 민족 10s 1024MB