Uncle Mike goes on various food adventures from town to town. Today he finds himself in food-topia, a land containing only restaurants, which are connected by bi-directional roads.

Uncle Mike wishes to visit a restaurant ~t~, but there are just so many temptations along the way - how could he resist the aroma of food waffing through the air! Everytime Mike passes by a restaurant, he must simply try it! But at the same time, he does not want to arrive at his destination too late and it is closed. Help uncle Mike find his way to restaurant ~t~ as quickly as possible!

Input

The first line contains ~n~, ~k~ - the number of restaurants, and the number of direct paths between two restaurants.

The next line contains ~s~, ~t~ that is the restaurant uncle Mike first started at, and the restaurant uncle Mike wants to get to.

The third line contains ~n~ numbers that is the eating time ~x~ at each restaurant.

The next ~k~ lines contains two restaurants ~u, v~ and the time ~d~ taken to go between them.

Output

Print a single number, that is the minimum amount of time needed for uncle Mike to arrive at restaurant ~t~.

Constraints

• ~2 \leq n \leq 100~
• ~1 \leq k \leq 10000~
• ~1 \leq u,v,s,t \leq n~
• ~1 \leq x, d \leq 100~
• ~s \neq t~
• It is guaranteed that there is at most one direct path between any two restaurants.
• It is guaranteed that there always exist a valid path between ~s~ and ~t~.

Example 1

Input

5 4
1 5
1 2 3 4 5
1 2 1
1 3 2
4 2 3
5 4 7

Output

18

Explanation

The restaurants and their connecting roads are depicted in the diagram below.

Mike starts at restaurant ~1~, and wants to travel to restaurant ~5~. In order to do so, he must spend ~11~ units of time travelling on the road, and ~1 + 2 + 4 = 7~ units of time eating at restaurants ~1~, ~2~ and ~4~ along the way.

Example 2

Input

6 9
3 4
2 17 8 6 9 3
1 2 6
1 3 10
1 4 21
2 3 5
2 5 7 
3 6 11
4 5 31
4 6 4
5 6 28

Output

26

Explanation

The restaurants and their connecting roads are depicted in the diagram below.

Mike starts at restaurant ~3~, and wants to travel to restaurant ~4~. In order to do so, he can travel through vertex ~6~. This takes ~15~ units of time on the road, and ~11~ units of time eating at restaurants ~3~ and ~6~.