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

진주 나들이를 온 보선이는 경상국립대 정문 쪽 연못 산책길에서 울고 있는 동기 원우를 만났다. 보선이가 다가가 이유를 묻자, 원우는 울면서 교수님의 심부름을 설명했다. 경상국립대에서 출발해 대학 주변의 모든 동네에 가서 하늘 사진을 찍고, 다시 경상국립대로 돌아오라는 것이었다. 원우는 거절하지 못했지만 심부름을 어떻게 끝내야 할지 모르겠다고 했다. 약간 모자라지만 착한 원우를 위해 보선이가 대신 심부름을 맡기로 했다.

경상국립대 주변에 있는 동네는 총 $N$개이며, 1번부터 $N$번까지 번호가 붙어 있다. 보선이는 편의상 경상국립대를 $N+1$번 지점으로 본다. 각 동네는 한 번씩만 방문할 수 있다. 하늘 사진을 찍으러 출발하면 필요한 사진을 모두 찍기 전까지는 경상국립대로 돌아올 수 없다. 경상국립대와 동네 $N$개 가운데 서로 다른 두 지점을 잇는 단방향 도로가 $M$개 있다. 시작 지점과 도착 지점이 같은 도로가 두 개 이상 존재할 수 있다.

교수님은 당부를 하나 더 하셨다. 임의의 두 하늘 사진은 찍은 시각에 차이가 있어야 하고, 어떤 동네의 하늘 사진은 그 동네에 정해진 다른 동네의 하늘 사진보다 늦게 찍어야 한다. 보선이는 심부름을 최대한 빨리 마치려고 한다. 하늘 사진을 찍는 데 걸리는 시간은 무시한다. 심부름을 마치는 데 걸리는 시간의 최솟값을 구하라.

첫 줄에 동네의 개수 $N$과 단방향 도로의 개수 $M$이 공백으로 구분되어 주어진다. $(1 \le N \le 14; 1 \le M \le 200)$

둘째 줄에는 $P_1, \dots, P_N$이 공백으로 구분되어 주어진다. 이는 $i$번 동네의 하늘 사진을 $P_i$번 동네의 하늘 사진보다 늦게 찍어야 한다는 뜻이다. $i = P_i$이면 $i$번 동네에서 사진을 찍는 시점은 상관없다. $(1 \le P_i \le N)$

셋째 줄부터 $M$개의 줄에 걸쳐 각 단방향 도로의 정보 $u_i$, $v_i$, $w_i$가 공백으로 구분되어 주어진다. $i$번째 도로는 시작 지점이 $u_i$, 끝 지점이 $v_i$이며, 도로를 지나는 데 $w_i$의 시간이 걸린다. $1$번부터 $N$번까지는 동네이고, $N+1$번 지점은 경상국립대이다. $(1 \le u_i, v_i \le N+1; u_i \ne v_i; 1 \le w_i \le 100)$

입력의 모든 수는 정수이다.

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