마을에는 N개의 교차로가 있으며 1에서 N까지 번호가 매겨져 있다. 또한 M개의 경로가 있으며 1에서 M까지의 번호가 붙어 있다.

각 도로는 두 개의 서로 다른 교차로를 양방향으로 연결한다. 도로 i (1≤i≤M)는 교차점 A_i와 교차점 B_i를 연결한다. 두 개의 다른 도로는 동일한 교차로 세트를 연결하지 않는다.

이 도로에는 1 이상 M 이하의 정수로 표현되는 색이 칠해져 있으며, 도로 i의 현재 색은 C_i이다. 여러 경로가 같은 색으로 칠해 질 수 있다.

지나는 마을의 교차로를 이동하는 로봇을 개발했다. 이 로봇에게 도로의 색을 지시하면 로봇은 지정된 색의 도로를 통과하여 인접한 교차로로 이동한다.

다만, 로봇이 현재 있는 교차로로 이어진 길 가운데, 지시된 색의 도로가 2개 이상 존재하면, 다음으로 진행할 길을 판별할 수 없게 되어 정지해 버린다.

당신의 목적은 현재 교차로 1에 있는 로봇에 지시를 여러 번 내려서 교차로 N으로 이동 시키는 것이다.

다만, 현재의 도로의 색으로는 그것이 불가능 할 수도 있기 때문에, 몇 개의 도로의 색을 바꾸는 것으로, 로봇을 교차점 N으로 이동 시킬 수 있는지 알고 싶다. 도로 i (1 ≤ i ≤ M)를 1 이상 M 이하의 좋아하는 정수의 색으로 바꾸기 위해서는 P_i원을 사용하여야 한다.

교차로와 도로 정보가 주어지면 필요한 금액의 최솟값을 찾는 프로그램을 작성하시오.

단, 도로의 색을 어떻게 바꾸어도 로봇을 교차로 N으로 이동 시킬 수 없는 경우에는 대신에 -1을 출력하라.

#5869 upload - done - how_to_reg - call_split Subtask

교차로 이동 로봇 timer 2s memory 1024MB

#5869
Subtask

교차로 이동 로봇 2s 1024MB