Minimum Delivery Cost

You are given a set of houses connected by bidirectional roads. Each house i has an associated delivery cost C_i. Starting from house s, your task is to find a path to house t such that the sum of the delivery costs (including the starting and ending houses, as well as any houses visited in between) is minimized. The roads connect pairs of houses and you may travel along any road in either direction.

Formally, you are given an undirected graph with n nodes and m edges. Each node i (1-indexed) has a cost C_i. Starting from house s, you want to travel to house t with the path cost defined as the sum of the costs for each house visited (including s and t). You need to output the minimum possible cost required to deliver the package.

Note: It is guaranteed that there exists at least one path from house s to house t.

inputFormat

The input is given from standard input in the following format:

n m s t
C1 C2 ... Cn
u1 v1
...
 um vm

where:

• n (2 ≤ n ≤ 1000) is the number of houses.
• m (1 ≤ m ≤ 5000) is the number of roads.
• s and t (1 ≤ s, t ≤ n) are the starting and target house indices, respectively.
• C_i (1 ≤ C_i ≤ 1000) is the delivery cost for house i.
• Each of the next m lines contains two integers u and v representing a bidirectional road between houses u and v.

outputFormat

Output a single integer: the minimum delivery cost to reach house t from house s.

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

3