30975번 - 약간 모자라지만 착한 친구야

문제

진주 나들이를 온 보선이는 경상국립대 정문 쪽 연못 산책길을 걷다가 울고 있는 동기 원우를 발견했다. 반가움보다 안쓰러움이 앞선 보선이는 원우한테 다가가서 울고 있는 이유를 물어봤다. 원우는 울면서 "교수님께서 경상국립대에서 출발해 경상국립대 주변에 있는 모든 동네에 가서 하늘 사진을 찍은 다음, 다시 경상국립대로 돌아오라는 심부름을 시키셨는데 거절을 못했어. 그런데 어떻게 심부름을 끝내야 할지 모르겠어."라고 대답했다. 약간 모자라지만 착한 원우를 위해 보선이가 대신 심부름을 맡기로 했다.

경상국립대 주변에 있는 동네는 총 $N$개이며, 각 동네는 1ドル$번부터 차례대로 번호가 부여되어 있다. 또한, 보선이는 편의상 경상국립대가 $N+1$번이라 생각하기로 했다. 모든 동네는 한 번씩만 방문이 가능하며, 하늘 사진을 찍으러 출발하고 나서는 필요한 모든 하늘 사진을 찍기 전까지 경상국립대로 돌아올 수 없다. 그리고 경상국립대와 동네 $N$개 중 서로 다른 두 지점을 잇는 단방향 도로 $M$개가 있다. 시작 지점과 도착 지점이 모두 동일한 도로가 두 개 이상 존재할 수 있다.

추가적으로 교수님의 또 다른 부탁이자 당부가 있었다. 이는 임의의 두 하늘 사진의 시간적 차이가 필요함의 이유로, 어떤 동네의 하늘 사진은 그 동네에 정해진 다른 동네의 하늘 사진보다 늦게 찍어야 한다는 것이었다.

보선이는 성공적인 진주 나들이를 위해 심부름을 최대한 빠르게 마치기로 결심했다. 심부름을 마치는 데 걸리는 시간의 최솟값을 구해보자. 하늘 사진을 찍는 데 걸리는 시간은 무시하자.

입력

첫 번째 줄에는 경상국립대 주변에 있는 동네의 개수 $N,ドル 임의의 두 동네 사이를 잇는 단방향 도로의 개수 $M$이 공백으로 구분되어 주어진다. $(1 ≤ N ≤ 14; 1 ≤ M ≤ 200)$

두 번째 줄에는 $P_1,ドル $\dots,ドル $P_N$이 공백으로 구분되어 주어진다. 이는 $i$번 동네의 하늘 사진은 $P_i$번 동네의 하늘 사진보다 늦게 찍어야 한다는 것을 의미한다. $i = P_i$인 경우에는 $i$번 동네에서 사진을 찍는 시점은 어느 때나 상관이 없다는 것을 의미한다. $(1 ≤ P_i ≤ N)$

세 번째 줄부터 $M$개의 줄에 걸쳐 각 단방향 도로의 정보 $u_i,ドル $v_i,ドル $w_i$가 공백으로 구분되어 주어진다. 이는 $i$번째 도로는 시작 지점이 $u_i,ドル 끝 지점이 $v_i$번이며 도로를 지나는 데 걸리는 시간은 $w_i$임을 의미한다. 1ドル,ドル $\dots,ドル $N$번 지점은 1ドル,ドル $\dots,ドル $N$번 동네를 뜻하며, $N+1$번 지점은 경상국립대를 뜻한다. $(1 ≤ u_i, v_i ≤ N + 1; u_i \neq v_i; 1 ≤ w_i ≤ 100)$

입력으로 주어지는 모든 수는 정수이다.

출력

첫 번째 줄에 심부름을 마치는 데 걸리는 시간의 최솟값을 출력한다. 만약 심부름을 마칠 수 없다면 –1을 출력한다.

제한

힌트