a180285 loves skiing. He arrives at a snowy mountain where there are $M$ ski tracks and $N$ intersections between tracks (which are also points of interest). Each point is assigned an index $i$ ($1 \le i \le N$) and an altitude $H_i$. a180285 can ski from point $i$ to point $j$ if and only if there is an edge between $i$ and $j$, and the altitude of $i$ is not less than the altitude of $j$.

Unlike other ski enthusiasts, a180285 likes to visit as many points as possible using the shortest total skiing distance. If he only visits points along a single path, he feels the number of points is too small. Therefore, a180285 takes out his portable time capsules. This is a magical medicine that, once consumed, allows him to immediately return to a previously visited point (without moving and without adding to the distance a180285 has skied). Please note that this magical medicine can be consumed consecutively, meaning he can return to points visited much earlier (such as the point visited before the last one, or even earlier).

Now, a180285 is standing at point 1, looking at the target at the bottom of the mountain, feeling excited. He wants to know, without considering the consumption of the time capsules, the strategy to visit the maximum number of points with the shortest total skiing distance (i.e., minimizing the total skiing distance while satisfying the condition of visiting the maximum number of points). Can you help him find the maximum number of points and the minimum total distance?

Input

The first line contains two integers $N$ and $M$.

The next line contains $N$ integers $H_i$, representing the altitude of each point.

The next $M$ lines describe the distribution of tracks between points. Each line contains three integers $U_i$, $V_i$, and $K_i$, representing a track of length $K_i$ between point $U_i$ and point $V_i$.

Output

Output a single line containing two integers: the maximum number of points a180285 can reach, and the minimum total skiing distance to reach them.

Constraints

For 30% of the data, $1 \le N \le 2000$.

For 100% of the data, $1 \le N \le 100000$.

For all data, $1 \le M \le 1000000$, $1 \le H_i \le 1000000000$, $1 \le K_i \le 1000000000$.

Examples

Input 1

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

Output 1

3 2