A survey team has decided to visit all cities to collect some data. There are N cities. All Cities are connected by M Bi-directional roads. Any one who want to use a road any number of times has to pay a one-time Road Tax. Each Road has a given Road Tax.

Every city belongs to a some particular state. States are numbered in increasing order starting from 1. In any state, Roads are made in a way that one can visit all the cities of that state without having to enter some other state. The Survey team can enter each state only in increasing order of the states number. There will always be at least one road connecting state i and state i+1.

The survey team can start from any city in state 1, and travel all the states and cities following the above conditions. They want to plan their route such that it minimizes the total Road tax they need to pay. Can you help them!

Find the Minimum Total Road Tax they need to pay.

Input Format

First Line contains N, M.

Next N lines contain one positive integer s[i], where i is the number of the city and s[i] is the number of state it belongs to.

Next M lines contains u, v, w. a Road connecting u and v, having a Road Tax of w.

Output Format

Output the Minimum Total Road Tax the Survey team would have to Pay.

Constraints

1 <= N <= 10^5

1<= M <= 2*10^5

1<= w <= 10000, Road tax of any road.

1<= s <=N, Number of States.

Setter: Vineet Mehta