P2469 [SDOI2010] Interstellar Race

The once-in-a-decade Milky Way Grand Prix is about to begin. As one of the biggest events in the galaxy, winning this championship is undoubtedly the dream of many. Youyou from the Jason constellation’s $\alpha$ star is one of them. The racecourse consists of $N$ planets and $M$ bidirectional interstellar routes. Each planet has a distinct gravity value. The race requires drivers to start from a celestial body that has no interstellar route to any of these $N$ planets, visit each of the $N$ planets exactly once, and the first to achieve this wins. Thanks to the very open rules, many contestants drive all sorts of homemade vehicles. This time, Youyou is driving a car named “Super E-Donkey,” a dream machine embodying the most cutting-edge technology in the galaxy. As a pinnacle of technology, the Super E-Donkey has two movement modes: High-Speed Sailing mode and Ability Burst mode. In High-Speed Sailing mode, it deploys an antimatter engine to speed along interstellar routes at many times the speed of light. In Ability Burst mode, it breaks free from the constraints of spacetime and uses psychic power for spatial jumps—after a period of positioning, it can instantly teleport to any planet. Unfortunately, on the day before the race, the Super E-Donkey was damaged in an ion storm, causing some malfunctions: when using High-Speed Sailing mode, it can only fly from any planet to a planet with strictly greater gravity; otherwise, the car will explode. Even though his beloved car has issues, Youyou still believes he can win. He has found the wisest sage in the galaxy—you. Please plan a racing scheme for him so that he can finish the race in the minimum possible time.

The first line contains two positive integers $N, M$. The second line contains $N$ integers $A_1,\cdots,A_N$, where $A_i$ is the positioning time required to reach planet $i$ using Ability Burst mode. Each of the next $M$ lines contains three positive integers $u_i, v_i, w_i$, indicating that there is a bidirectional interstellar route between planets $u_i$ and $v_i$ that takes $w_i$ time to traverse. The input is already sorted by gravity, meaning that a smaller-indexed planet has smaller gravity, and no two planets have the same gravity.

Output a single integer: the minimum time required to finish the race.

Explanation for Sample 1: First use Ability Burst mode to reach planet $1$, costing time $1$. Then switch to High-Speed Sailing mode and travel to planet $2$, costing time $10$. After that, continue to planet $3$ to finish the race, costing time $1$. Although going from planet $1$ to $3$ and then to $2$ seems better, we cannot do that because it would cause the Super E-Donkey to explode. Constraints - For $30\%$ of the testdata, $N \leq 20$, $M \leq 50$. - For $70\%$ of the testdata, $N \leq 200$, $M \leq 4 \times 10^3$. - For $100\%$ of the testdata, $N \leq 800$, $M \leq 1.5 \times 10^4$. - Every number in the input is between $1$ and $10^6$. - There is at most one route between any pair of planets, and there are no self-loops. Translated by ChatGPT 5