The decennial Galactic Racing Tournament is about to begin. As one of the grandest events in the galaxy, winning the championship is a dream for many, including Youyou from the planet $\alpha$ in the constellation Jason.

The race takes place across $N$ planets and $M$ bidirectional interstellar routes, where each planet has a unique gravitational value. The rules require racers to start from a celestial body that has no routes connected to any of the $N$ planets, and visit each of the $N$ planets exactly once. The first person to complete this goal wins.

Due to the very open nature of the competition, many people participate with all sorts of strange homemade racing vehicles. This time, Youyou is driving a racing car called the "Super Electric Donkey," a dream machine that embodies the most cutting-edge technology in the galaxy. As a product of high technology, the Super Electric Donkey has two movement modes: High-Speed Navigation Mode and Ability Burst Mode. In High-Speed Navigation Mode, the Super Electric Donkey deploys an antimatter engine to travel along interstellar routes at several times the speed of light. In Ability Burst Mode, the Super Electric Donkey breaks free from the constraints of space and time, using superpowers to perform space 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 an ion storm, resulting in some functional impairments: when using High-Speed Navigation Mode, it can only fly from a planet to a planet with a higher gravitational value; otherwise, the racing car will explode.

Although his beloved racing car has problems, Youyou still firmly believes that he can win. He has found the smartest sage in the galaxy—you—and asks you to arrange a race plan for him so that he can complete the race in the minimum amount of time.

Input

The first line contains two positive integers $N, M$.

The second line contains $N$ integers $A_1 \sim A_N$, where $A_i$ represents the positioning time required to reach planet $i$ using Ability Burst Mode.

The next $M$ lines each contain 3 positive integers $u_i, v_i, w_i$, representing an interstellar route between planet $u_i$ and planet $v_i$ that takes $w_i$ time to traverse.

The input data is already sorted by gravitational value, meaning that a planet with a smaller index always has a smaller gravitational value, and no two planets have the same gravitational value.

Output

A single integer representing the minimum time required to complete the race.

Examples

Input 1

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

Output 1

12

Note 1

First, use Ability Burst Mode to reach planet 1, costing 1. Then switch to High-Speed Navigation Mode to travel to planet 2, costing 10. Finally, continue to travel to planet 3 to complete the race, costing 1. Although it seems better 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.

Input 2

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

Output 2

6

Note 2

In this example, we always use Ability Burst Mode to complete the race.

Input 3

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

Output 3

230

Constraints

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

For 70% of the data: $N \le 200, M \le 4000$;

For 100% of the data: $N \le 800, M \le 15000$. 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 there are no routes from a planet to itself.