Interstellar Racing

Problem Source

SDOI 2010

Problem Description

The galactic racing championship, held once every 10 years, is about to begin again. As one of the grandest events in the whole galaxy, winning this event is the dream of many, and Yoyo from planet Alpha of the constellation Centaurus is one of them.

The race track consists of $N$ planets connected by $M$ bidirectional interstellar routes, and each planet has a different gravitational value. The rules require a racer to start from a celestial body that has no route to any of these $N$ planets, visit each of the $N$ planets exactly once, and the first to achieve this wins.

Because the format is very open, many people drive all kinds of bizarre homemade racers to compete. This time Yoyo's racer is called the "Super Electric Donkey," a dream machine embodying the most cutting-edge technology of the entire galaxy. As the pinnacle of high technology, the Super Electric Donkey has two movement modes: high-speed sailing mode and ability-burst mode. In high-speed sailing mode, the donkey unfolds its antimatter engine and sails along interstellar routes at several times the speed of light. In ability-burst mode, the donkey breaks free from the shackles of space-time, using its superpower to perform a space jump — after a period of positioning, it can instantly move to any planet.

Against all odds, the day before the race the Super Electric Donkey was damaged in an ion storm and developed a malfunction: in high-speed sailing mode it can only fly from a planet to another planet with a greater gravitational value, otherwise the racer explodes.

Despite the problem with his beloved racer, Yoyo still believes he can win. He has found the wisest sage in the galaxy — you — and asks you to arrange a race plan for him that completes the race in the least time.

Input Format

The first line contains two positive integers $N, M$ ($N \leq 800,\ M \leq 1.5 \times 10^4$).

The second line contains $N$ numbers $A_1, \dots, A_N$, where $A_i$ is the positioning time required to reach planet $i$ using ability-burst mode.

The next $M$ lines each contain three positive integers $u_i, v_i, w_i$, indicating a bidirectional interstellar route between planets $u_i$ and $v_i$ that takes $w_i$ time to sail.

The input data is already sorted by gravitational value, i.e. a planet with a smaller index always has a smaller gravitational value, and no two planets share the same gravitational value. It is guaranteed that there is at most one route between any two planets, and no planet has a route to itself.

Every number in the input is at most $10^6$.

Output Format

Output a single positive integer: the minimum time needed to complete the race.

Sample Input 1

3 3
1 100 100
2 1 10
1 3 1
2 3 1

Sample Output 1

12

Sample Input 2

3 3
1 2 3
1 2 100
1 3 100
2 3 100

Sample Output 2

6

Sample Input 3

4 5
100 1000 10 100
1 2 100
2 3 100
4 3 100
1 3 20
2 4 20

Sample Output 3

230

Hint

Sample 1 explanation: first use ability-burst mode to reach planet $1$, costing $1$ unit of time. Then switch to high-speed sailing mode and sail to planet $2$, costing $10$. Then continue sailing to planet $3$ to finish, costing $1$. Although going $1 \to 3 \to 2$ looks better, we cannot do that, because that would make the Super Electric Donkey explode.