P2573 [SCOI2012] Skiing

a180285 is very fond of skiing. He comes to a snowy mountain with $m$ ski tracks and $n$ intersections between tracks (which are also scenic spots). Each scenic spot has an index $i\space (1 \le i \le n)$ and a height $h_i$. a180285 can ski from spot $i$ to spot $j$ if and only if there is an edge between $i$ and $j$, and the height at $i$ is **not less than** that at $j$. Unlike other ski enthusiasts, a180285 prefers to visit as many spots as possible using the shortest skiing route. If he only visits the spots along a single path, he feels the number is too small. So a180285 takes out his portable time capsule. It is a magical medicine that, after being taken, can immediately return him to the last visited spot (this does not require movement and is not counted in a180285’s skiing distance). Note that this magical medicine can be taken consecutively, allowing him to return to spots visited a longer time ago (for example, the previous, the one before that, or the one even earlier). Now, a180285 stands at spot $1$, gazing at the goals downhill, full of excitement. He wants to know, ignoring the consumption of time capsules, the plan that uses the shortest skiing distance to reach as many scenic spots as possible (i.e., among all plans that maximize the number of visited spots, minimize the total skiing distance). Can you help him find the minimum distance and the number of spots?

The first line contains two integers $n, m$. The next line contains $n$ integers $h_i$, representing the height of each scenic spot. Then there are $m$ lines, each with three integers $u, v, k$, indicating there is a track of length $k$ between spots $u$ and $v$.

Output one line with two integers: the maximum number of scenic spots a180285 can reach, and the minimum total skiing distance in that case.

For $30\%$ of the testdata, $1 \le n \le 2000$. For $100\%$ of the testdata, $1 \le n \le 10^5$, $1 \le m \le 10^6$, $1 \le h_i \le 10^9$, $1 \le k_i \le 10^9$. Translated by ChatGPT 5