A Slightly Slow but Kind Friend

Bosun, who came to Jinju for an outing, found his classmate Wonwoo crying on a pond path near the front gate of Gyeongsang National University. Bosun walked over and asked why. Wonwoo explained through tears that the professor had sent him on an errand: start at Gyeongsang National University, visit every neighborhood around it to take sky photos, then return to the university. He could not refuse, but he did not know how to finish it. For the slightly slow but kind Wonwoo, Bosun decided to take over the errand.

There are $N$ neighborhoods around Gyeongsang National University, numbered 1 to $N$. For convenience, Bosun treats the university as point $N+1$. Each neighborhood can be visited only once. After leaving the university to take sky photos, he cannot return to it until all required photos are taken. There are $M$ one-way roads, each connecting two different points among the university and the $N$ neighborhoods. Two or more roads may have the same start and end points.

The professor gave one more instruction. Any two sky photos must be taken at different times, and the photo of a neighborhood must be taken later than the photo of the neighborhood assigned to it. Bosun wants to finish the errand as fast as possible. Ignore the time needed to take the photos. Find the minimum time to finish the errand.

The first line contains $N$ and $M$, separated by a space. $(1 \le N \le 14; 1 \le M \le 200)$

The second line contains $P_1, \dots, P_N$, separated by spaces. This means the sky photo of neighborhood $i$ must be taken later than the sky photo of neighborhood $P_i$. If $i = P_i$, the time of the photo in neighborhood $i$ can be anything. $(1 \le P_i \le N)$

From the third line onward, $M$ lines each give a one-way road $u_i$, $v_i$, $w_i$, separated by spaces. The $i$-th road starts at $u_i$, ends at $v_i$, and takes $w_i$ time to traverse. Points $1$ to $N$ are the neighborhoods, and point $N+1$ is the university. $(1 \le u_i, v_i \le N+1; u_i \ne v_i; 1 \le w_i \le 100)$

All numbers in the input are integers.

Print the minimum time to finish the errand on the first line. If the errand cannot be finished, print -1.