Hasan lives in an area of islands where many islands are connected by bridges. In this area of islands, there are three independent unions of islands: ANANAS, KIWI, and MANGO. Each island is either independent or a member of one of the three existing unions of islands within the discretion of that islands' inhabitants. A fruit unique to that union is grown on each island that is a member of the Union.

In preparation for the upcoming Fruit Salad Festival, the inhabitants of the islands want to include fruits grown in other unions in these festivals in order to prepare better fruit salads, and therefore there is a campaign of fruit transport in the region of the islands. Hasan wants to move pineapple from an island in the ANANAS Union with his truck to an island in the KIWI Union, and then move kiwi from that island to an island in the MANGO Union.

If there exists a path, Hasan is allowed to move between any islands. Can you help Hasan, who wants to consume as little fuel as possible with his truck, find the least amount of fuel he will consume to transport fruit from any ANANAS Island to any KIWI Island, and then from that island to any MANGO island?

Input

The first line contains the numbers \(\mathbf{N}\), \(\mathbf{M}\), which indicate how many islands there are and how many bridges there are between these islands respectively.

In the second line, there is a sequence of \(\mathbf{C}\) with \(\mathbf{N}\) numbers. The element in the array \(\mathbf{C_i}\) indicates which union the island with the index i belongs to. The union memberships of the islands are given as follows:

• Members of the ANANAS union with the number 1
• Members of the KIWI union with the number 2
• Members of the MANGO union with the number 3
• Independent islands are shown with the number 4.

The next \(\mathbf{M}\) line each represents a bridge, and each line contains the numbers \(\mathbf{A}\), \(\mathbf{B}\), and \(\mathbf{W}\). The bridge on this line is \(\mathbf{W}\) in length and connects the islands \(\mathbf{A}\) and \(\mathbf{B}\).

• \(1 \leq \mathbf{N}, \mathbf{M} \leq 10^5\)
• \(1 \leq \mathbf{C_i} \leq 4\)
• \(1 \leq \mathbf{A}, \mathbf{B} \leq \mathbf{N}\)
• \(1 \leq \mathbf{W} \leq 10^5\)

Output

Print the minimum distance between one of the ANANAS islands to one of the MANGO islands provided that at least one of the KIWI islands has been visited through the path.

• If this path cannot be completed in any way, print "-1".

Examples

Input 1:

3 2
1 2 3 
1 2 2
2 3 3

Output 1:

5

Input 2:

5 5
1 2 3 4 4
4 2 3
5 3 3
2 5 5
3 4 4
1 4 2

Output 2:

12

Explanation

Input 1

• Start from 1st island which is an ANANAS island and cross the 1st bridge with a length of 2.
• Use the 2nd bridge with a length of 3 and move from KIWI island to the MANGO island. Total distance 5.

Input 2

• Move from 1st island to 4th island by 5th bridge. Total distance 2.
• Move from 4th island to 2nd island by 1st bridge. Total distance 5.
• Move from 2nd island to 4th island by 1st bridge. Total distance 8.
• Move from 4th island to 3rd island by 4th bridge. Total distance 12.