Problem Description

The Galactic Racing Championship, held once every ten years, is about to commence. As one of the most significant events in the galaxy, winning this championship is a dream for many, including Youyou from the Alpha star in the Jason constellation.

The racing venue consists of $N$ planets and $M$ bidirectional interstellar routes, with each planet having a unique gravitational value. The competition requires racers to start from a celestial body that has no routes to these $N$ planets, visit each of these planets exactly once, and the first to achieve this goal wins.

Due to the open nature of the competition, many participants drive homemade racing vehicles of various kinds. Youyou's vehicle, the Super Electric Donkey, is a dream racing car that embodies the pinnacle of galactic technology. As a product of the highest technology, the Super Electric Donkey has two modes of movement: high-speed navigation mode and burst mode. In high-speed navigation mode, the Super Electric Donkey deploys a antimatter engine, traveling at speeds several times the speed of light along interstellar routes. In burst mode, the Super Electric Donkey breaks free from the constraints of time and space, using superpowers for spatial jumps—after a period of positioning, it can instantly move to any planet.

Unfortunately, the day before the race, the Super Electric Donkey was damaged in a ion storm, resulting in some malfunctions: in high-speed navigation mode, it can only travel from each planet to planets with greater gravitational values, or else the vehicle will explode.

Despite the issue with his beloved vehicle, Youyou still believes he can win. He has sought the help of the wisest sage in the galaxy—you, to devise a racing strategy for him to complete the race in the shortest time possible.

Input Format

The first line of the input file starrace.in contains two positive integers $N, M$.

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

The following $M$ lines each contain three positive integers $u_i, v_i, w_i$, indicating the existence of an interstellar route that takes $w_i$ time to travel between planets numbered $u_i$ and $v_i$.

The input data is sorted by gravitational value, meaning planets with smaller numbers have smaller gravitational values, and no two planets have the same gravitational value.

Output Format

The output file starrace.out contains only one positive integer, representing the minimum time required to complete the race.

Sample Input and Output

Input Sample #1

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

Output Sample #1

12

Input Sample #2

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

Output Sample #2

6

Input Sample #3

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

Output Sample #3

230

Notes/Hints

Explanation of Sample 1: First, use burst mode to planet $1$, taking time $1$.

Then switch to high-speed navigation mode, travel to planet $2$, taking time $10$.

Continue traveling to planet $3$ to complete the race, taking time $1$.

Although it seems more optimal to go from planet $1$ to planet $3$ and then to planet $2$, we cannot do that because it would cause the Super Electric Donkey to explode.

Data Size and Constraints

For $30\%$ of the data, $N \leq 20$, $M \leq 50$;

For $70\%$ of the data, $N \leq 200$, $M \leq 4 \times 10^3$;

For $100\%$ of the data, $N \leq 800$, $M \leq 1.5 \times 10^4$.

Any number in the input data will not exceed $10^6$.

The input data guarantees that there is at most one route between any two planets and no route from a planet to itself.

见题面 Input 部分

见题面 Output 部分